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

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


Ответ

Можно.

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

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

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

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