Олимпиадная задача по теории чисел и комбинаторной геометрии для 9-11 классов
Задача
На отрезке [0, N] отмечены его концы и еще две точки так, что длины отрезков, на которые разбился отрезок [0, N], целые и взаимно просты в совокупности. Если нашлись такие две отмеченные точки A и B, что расстояние между ними кратно 3, то можно разделить отрезок AB на три равных части, отметить одну из точек деления и стереть одну из точек A, B. Верно ли, что за несколько таких действий можно отметить любую наперед заданную целую точку отрезка [0, N]?
Решение
Пусть M – целая точка на отрезке [0, N]. Приведём алгоритм, позволяющий её отметить. Назовём исходные точки A1, A2, A3, A4 и будем считать, что мы на шаге алгоритма заменяем одну из точек на новую и новую называем так же. При этом на каждом шаге алгоритма отрезки между отмеченными точками будут взаимно просты в совокупности и расстояние от M до заменяемой точки будет уменьшаться. Кроме того, каждая точка будет оставаться по ту же сторону от M, что и изначально (или перемещаться в M). Ясно, что такую процедуру можно проделать лишь конечное число раз, поэтому M в конце концов будет отмечена.
Перенумеруем отмеченные точки в произвольном порядке: B1, B2, B3, B4. Тогда наше условие взаимной простоты равносильно тому, что длины отрезков B1B2, B2B3, B3B4 взаимно просты в совокупности. Поэтому, если расстояние от заменяемой точки до какой-то из оставшихся уменьшилось в целое число раз, то взаимная простота сохранилась.
Координаты двух из четырёх отмеченных точек дают одинаковые остатки при делении на 3; пусть это точки Ai и Aj. Возьмём такие точки C и D, что
AiC = CD = DAj. Если точки C и D уже отмечены, то из взаимной простоты получаем AiC = CD = DAj = 1, и точка M отмечена, ибо лежит на AiAj . Если точка C отмечена, а D нет, то можно одну из точек Ai или Aj (в зависимости от положения M) заменить на D; при этом взаимная простота сохранится, ибо расстояние от заменённой точки до C останется неизменным или разделится на 2. Если отмечена только D, шаг аналогичен.
Пусть ни одна из точек C, D не отмечена. Если M и Ai лежат по одну сторону от C (симметричный случай аналогичен), то переместим Aj в C; при этом длина AiAj уменьшилась в три раза, и взаимная простота сохранилась. Пусть, наконец, M лежит на CD. Если длина AiAj чётна, то простые делители длины AiD являются простыми делителями AiAj, поэтому при перемещении Aj в D взаимная простота сохранится. Если же расстояние AiAj нечётно, то для любой третьей отмеченной точки Am одно из расстояний AiAm, AjAm (пусть AiAm) нечётно. Тогда можно заменить Aj на D; у нового расстояния AiAj лишь один новый простой делитель – 2, но НОД расстояний не может делиться на 2, поскольку AiAm нечётно.
Ответ
Верно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь