2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Задача на делимость
Сообщение25.08.2011, 00:13 
Аватара пользователя
"принцип Дирихле"

 
 
 
 Re: Задача на делимость
Сообщение25.08.2011, 00:57 
alcoholist в сообщении #477519 писал(а):
"принцип Дирихле"

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

 
 
 
 Re: Задача на делимость
Сообщение25.08.2011, 12:43 
Предположим, что данное множество не содержит кратных точек. Раскрасим точки из $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) получим отрезок, полностью окрашенный в синий цвет.

 
 
 
 В том же духе
Сообщение07.09.2011, 22:53 
Но полегче.
Доказат, что существует ряд из 1000 последовательных натуральных чисел, содержащий ровно 5 простых чисел.

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

 
 
 
 Re: Задача на делимость
Сообщение08.09.2011, 22:45 
Правильно, Cash.
Например ряд
1002!+2,1002!+3,....,1002!+1002.
Или НОК(2..1002)-1002,-1001...

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group