Олимпиадная задача по теории чисел и комбинаторной геометрии для 8–10 класса
Задача
На отрезке [0, 2002] отмечены его концы и n – 1 > 0 целых точек так, что длины отрезков, на которые разбился отрезок [0, 2002], взаимно просты в совокупности. Разрешается разделить любой отрезок с отмеченными концами на n равных частей и отметить точки деления, если они все целые. (Точку можно отметить второй раз, при этом она остаётся отмеченной.) Можно ли, повторив несколько раз эту операцию, отметить все целые точки на отрезке?
Решение
Будем отмечать новые точки по правилам до тех пор, пока это возможно. Тогда в конце концов мы получим ситуацию, когда каждый отрезок с длиной, кратной n, с концами в отмеченных точках уже разделён отмеченными точками на n равных частей. Покажем, что отмечены все целые точки.
Рассмотрим n соседних отрезочков A1A2, A2A3, ..., AnAn+1, на которые делят отмеченные точки исходный отрезок. Если остатки от деления на n длин отрезков A1Ak (2 ≤ k ≤ n + 1) различны, то среди них найдётся отрезок, длина которого делится на n; в противном случае два остатка, скажем, у A1Ak и A1Al, совпадают, и тогда длина AkAl делится на n. В любом случае, длина какого-то отрезка AiAj (i < j) делится на n. Тогда он уже поделён на n равных частей при помощи n – 1 точки. Но на этом отрезке нет отмеченных точек, кроме Am при i < m < j; поэтому такое может быть лишь при i = 1, j = n + 1 и A1A2 = A2A3 = ... = AnAn+1. Отсюда следует, что длины всех отрезочков разбиения равны.
Пусть их длина равна l. Тогда координаты всех исходно отмеченных точек кратны l; но они взаимно просты в совокупности, поэтому l = 1, то есть все целые точки отмечены.
Ответ
Можно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь