Разделы 
Дополнительно
Задача по математике - 1664
2019-01-20 
На отрезке $[0, N]$ отмечены его концы и еще 2 точки так, что длины отрезков, на которые разбился отрезок $[0,N]$, целые и взаимно просты в совокупности. Если нашлись две отмеченные точки $A$ и $B$ такие, что расстояние между ними кратно 3, то можно разделить отрезок $AB$ на 3 равных части, отметить одну из точек деления и стереть одну из точек $A, B$. Верно ли, что за несколько таких действий можно отметить любую наперед заданную целую точку отрезка $[0, N]$?
Решение:
Пусть $M$ - целая точка на отрезке $[0, N]$. Приведем алгоритм, позволяющий ее отметить. Назовем исходные точки $A_1, A_2, A_3, A_4$, и будем считать, что мы на шаге алгоритма заменяем одну из точек на новую и новую называем так же. При этом на каждом шаге алгоритма отрезки между отмеченными точками будут взаимно просты в совокупности и расстояние от $M$ до заменяемой точки будет уменьшаться. Кроме того, каждая точка будет оставаться по ту же сторону от $M$, что и изначально (или перемещаться в $M$). Ясно, что такую процедуру можно проделать лишь конечное число раз, поэтому $M$ в конце концов будет отмечена.
Перенумеруем отмеченные точки в произвольном порядке: $B_1, B_2, B_3, B_4$. Тогда наше условие взаимной простоты равносильно тому, что длины отрезков $B_1B_2, B_2B_3, B_3B_4$ взаимно просты в совокупности. Поэтому, если расстояние от заменяемой точки до какой-то из оставшихся уменьшилось в целое число раз, то взаимная простота сохранилась.
Координаты двух из четырех отмеченных точек дают одинаковые остатки при делении на 3; пусть это точки $A_i$ и $A_j$. Возьмем точки $C$ и $D$ такие, что $A_iC = CD = DA_j$. Если точки $C$ и $D$ уже отмечены, то из взаимной простоты получаем $A_iC = CD = DA_j = 1$, и точка $M$ отмечена, ибо лежит на $A_iA_j$. Если точка $C$ отмечена, а $D$ нет, то можно одну из точек $A_i$ или $A_j$ (в зависимости от положения $M$) заменить на $D$; при этом взаимная простота сохранится, ибо расстояние от замененной точки до $C$ останется неизменным или разделится на 2. Если отмечена только $D$, шаг аналогичен.
Пусть ни одна из точек $C, D$ не отмечена. Если $M$ и $A_i$ лежат по одну сторону от $C$ (симметричный случай аналогичен), то переместим $A_j$ в $C$; при этом длина $A_iA_j$ уменьшилась в три раза, и взаимная простота сохранилась. Пусть, наконец, $M$ лежит на $CD$. Если длина $A_iA_j$ четна, то простые делители длины $A_iD$ являются простыми делителями $A_iA_j$, поэтому при перемещении $A_j$ в $D$ взаимная простота сохранится. Если же расстояние $A_iA_j$ нечетно, то для любой третьей отмеченной точки $A_m$ одно из расстояний $A_iA_m, A_jA_m$ нечетно. Пусть, для определенности, $A_iA_m$ нечетно. Тогда можно заменить $A_j$ на $D$; у нового расстояния $A_iA_j$ лишь один новый простой делитель - 2, но НОД расстояний не может делиться на 2, поскольку $A_iA_m$ нечетно.
Ответ. Верно.
На отрезке $[0, N]$ отмечены его концы и еще 2 точки так, что длины отрезков, на которые разбился отрезок $[0,N]$, целые и взаимно просты в совокупности. Если нашлись две отмеченные точки $A$ и $B$ такие, что расстояние между ними кратно 3, то можно разделить отрезок $AB$ на 3 равных части, отметить одну из точек деления и стереть одну из точек $A, B$. Верно ли, что за несколько таких действий можно отметить любую наперед заданную целую точку отрезка $[0, N]$?
Решение:
Пусть $M$ - целая точка на отрезке $[0, N]$. Приведем алгоритм, позволяющий ее отметить. Назовем исходные точки $A_1, A_2, A_3, A_4$, и будем считать, что мы на шаге алгоритма заменяем одну из точек на новую и новую называем так же. При этом на каждом шаге алгоритма отрезки между отмеченными точками будут взаимно просты в совокупности и расстояние от $M$ до заменяемой точки будет уменьшаться. Кроме того, каждая точка будет оставаться по ту же сторону от $M$, что и изначально (или перемещаться в $M$). Ясно, что такую процедуру можно проделать лишь конечное число раз, поэтому $M$ в конце концов будет отмечена.
Перенумеруем отмеченные точки в произвольном порядке: $B_1, B_2, B_3, B_4$. Тогда наше условие взаимной простоты равносильно тому, что длины отрезков $B_1B_2, B_2B_3, B_3B_4$ взаимно просты в совокупности. Поэтому, если расстояние от заменяемой точки до какой-то из оставшихся уменьшилось в целое число раз, то взаимная простота сохранилась.
Координаты двух из четырех отмеченных точек дают одинаковые остатки при делении на 3; пусть это точки $A_i$ и $A_j$. Возьмем точки $C$ и $D$ такие, что $A_iC = CD = DA_j$. Если точки $C$ и $D$ уже отмечены, то из взаимной простоты получаем $A_iC = CD = DA_j = 1$, и точка $M$ отмечена, ибо лежит на $A_iA_j$. Если точка $C$ отмечена, а $D$ нет, то можно одну из точек $A_i$ или $A_j$ (в зависимости от положения $M$) заменить на $D$; при этом взаимная простота сохранится, ибо расстояние от замененной точки до $C$ останется неизменным или разделится на 2. Если отмечена только $D$, шаг аналогичен.
Пусть ни одна из точек $C, D$ не отмечена. Если $M$ и $A_i$ лежат по одну сторону от $C$ (симметричный случай аналогичен), то переместим $A_j$ в $C$; при этом длина $A_iA_j$ уменьшилась в три раза, и взаимная простота сохранилась. Пусть, наконец, $M$ лежит на $CD$. Если длина $A_iA_j$ четна, то простые делители длины $A_iD$ являются простыми делителями $A_iA_j$, поэтому при перемещении $A_j$ в $D$ взаимная простота сохранится. Если же расстояние $A_iA_j$ нечетно, то для любой третьей отмеченной точки $A_m$ одно из расстояний $A_iA_m, A_jA_m$ нечетно. Пусть, для определенности, $A_iA_m$ нечетно. Тогда можно заменить $A_j$ на $D$; у нового расстояния $A_iA_j$ лишь один новый простой делитель - 2, но НОД расстояний не может делиться на 2, поскольку $A_iA_m$ нечетно.
Ответ. Верно.
