ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 110092
Темы:    [ Системы точек ]
[ Процессы и операции ]
[ НОД и НОК. Взаимная простота ]
[ Деление с остатком ]
Сложность: 4
Классы: 9,10,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 нечётно.


Ответ

Верно.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2002
Этап
Вариант 4
Класс
Класс 11
задача
Номер 02.4.11.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .