Question

На отрезке ABAB мистер Фокс отметил 169 точек , которые разделили отрезок на 170 равных частей; а мистер Форд отметил 112 точек, которые разделили отрезок ABAB на 113 равных частей. Все отмеченные точки, вместе взятые, разбили отрезок ABAB на много маленьких отрезочков, и Форд с Фоксом совместными усилиями измерили длины всех получившихся отрезочков между соседними точками (концы исходного отрезка они тоже считали отмеченными точками). Сколько различных длин получили Фокс с Фордом?

Answer 1

Пусть AB=[0;170]. Тогда можно считать, что точки Фокса - все целые точки на этом отрезке, а k-ая точка Форда имеет координаты 170k/113, где k=0,1,2,...,112. Точку Форда можно записать в виде q+r/113, где q - частное, а r - остаток от деления 170k на 113. Т.к. расстояние между соседними точками Форда равно 170/113, что больше 1, то ближайшими к точкам Форда будут точки Фокса, и значит расстояние от k-ой точки Форда до соседней слева равно r/113, а до соседней справа (113-r)/113. Значит максимальное количество различных расстояний не больше, чем остатков от деления на 113, т.е. не более 113 штук.

Т.к.  НОД(170,113)=1, то, когда k пробегает все числа от 0 до 112, остаток r от деления 170k на 113 пробегает те же числа, но в другом порядке, а значит все 113 возможных расстояний будут достигаться на каких-то соседних точках. Ответ: 113.

Answer 2

Для решения этой задачи мы можем использовать принцип деления отрезка на равные части и затем подсчитать, сколько различных длин отрезков получили Фокс и Форд.

Фокс разделил отрезок на 170 равных частей, а Форд разделил его на 113 равных частей. Это значит, что Фокс и Форд пометили точки с интервалом длиной:

Для Фокса: длина_отрезка / 170 Для Форда: длина_отрезка / 113

Теперь мы можем вычислить длины всех отрезков между соседними точками, начиная с конца ABAB и двигаясь к началу. Начнем с Фокса:

Длина_отрезка_1 = длина_отрезка Длина_отрезка_2 = длина_отрезка - (длина_отрезка / 170) Длина_отрезка_3 = длина_отрезка - 2 * (длина_отрезка / 170) ... Длина_отрезка_169 = длина_отрезка - 168 * (длина_отрезка / 170)

Теперь перейдем к Форду:

Длина_отрезка_1 = длина_отрезка Длина_отрезка_2 = длина_отрезка - (длина_отрезка / 113) Длина_отрезка_3 = длина_отрезка - 2 * (длина_отрезка / 113) ... Длина_отрезка_112 = длина_отрезка - 111 * (длина_отрезка / 113)

Теперь у нас есть списки длин всех отрезков для Фокса и Форда. Мы можем подсчитать, сколько различных длин у них получилось, используя множества (чтобы учесть только уникальные значения):

Количество_различных_длин_Фокса = len(set([Длина_отрезка_1, Длина_отрезка_2, ..., Длина_отрезка_169])) Количество_различных_длин_Форда = len(set([Длина_отрезка_1, Длина_отрезка_2, ..., Длина_отрезка_112]))

Теперь можно вычислить эти значения:

Количество_различных_длин_Фокса = 170 Количество_различных_длин_Форда = 113

Итак, Фокс и Форд получили 170 различных длин и 113 различных длин соответственно.