Задача на делимость

[Verka-Serdyuchka]

Множество натуральных чисел A таково, что среди любых 1000 подряд идущих натуральных чи-
сел встретится число из A. Докажите, что в A найдутся два числа, одно из которых делится
на другое.

[alcoholist]

"принцип Дирихле"

[Verka-Serdyuchka]

alcoholist в сообщении #477519 писал(а):

"принцип Дирихле"

И что?
Ну найдутся два числа, дающие одинаковые остатки при делении на 1000. Но это же не означает, что одно делится на другое. Например, 1007 не делится на 7.

[Cash]

Предположим, что данное множество не содержит кратных точек. Раскрасим точки из $A$ в красный цвет. Неокрашенные точки, кратные какому либо числу из $A$, покрасим в синий цвет. Очевидно, что если $x$ - синяя точка, то точка $kx$, для любого натурального $k$, также синяя.
Рассмотрим произвольный отрезок $[aа, a+999]$. По условию, на нем есть одна красная точка $x$. Пусть на нем также $n $ синих точек $x_1, x_2, \dots, x_n$. Сдвинем отрезок на величину $x_1x_2\dots x_nx$. На новом отрезке также должна быть красная точка, а в синий цвет уже будет окрашено, как минимум, $n+1$ точек, так как синие точки перейдут в синие, а красная в синюю. Повторяя эту процедуру достаточное количество раз (не более 1000) получим отрезок, полностью окрашенный в синий цвет.

[Shadow]

Но полегче.
Доказат, что существует ряд из 1000 последовательных натуральных чисел, содержащий ровно 5 простых чисел.

[Cash]

Взяв некоторую тысячу последовательных чисел и прибавив единицу ко всем, мы получим новый набор в котором количество простых чисел отличается не более чем на единицу. Остается заметить что существует 1000 последовательных составных чисел, а среди первой тысячи простых больше 5.

[Shadow]

Правильно, Cash.
Например ряд
1002!+2,1002!+3,....,1002!+1002.
Или НОК(2..1002)-1002,-1001...