|
|
 |
Условие
Некоторые натуральные числа отмечены. Известно, что на каждом отрезке числовой прямой длины 1999 есть отмеченное число.
Докажите, что найдётся пара отмеченных чисел, одно из которых делится на другое.
Решение
Рассмотрим отрезки натурального ряда длины 1999. Все они отличаются сдвигом. Назовём точки, или позиции, на двух таких отрезках соответствующими, если они совмещаются при сдвиге одного отрезка на другой.
Предположим, что ни одно из отмеченных чисел не делится на другое.
Рассмотрим отрезок [1, 1999]. По условию в нём есть отмеченное число, скажем x1. Сдвинем этот отрезок на x1. На позиции, соответствующей числу x1, не может стоять отмеченное число (так как оно делится на x1), но в этом отрезке есть какое-то другое отмеченное число x2. Сдвинем новый отрезок на x1x2. Тогда на позициях, соответствующих отмеченным числам x1 и x2 не могут стоять отмеченные числа (так как эти числа делятся на x1 и x2 соответственно), но на этом отрезке есть некоторое отмеченное число x3.
Сдвинем новый отрезок на x1x2x3, найдём новое число x4 и т.д. На шаге с номером t мы осуществляем сдвиг на x1...xt и получаем отрезок с t запретами. На шаге с номером 1999 мы получим, что все позиции запрещены, что противоречит условию.
