Теорема Эрдеша.

Среди первых n натуральных чисел выбрано более, чем (n+1)/2 различных. Докажите, что одно из них делится на другое.

Доказательство.

Заметим, что различных нечетных делителей у этих чисел не более (n+1)/2, т.е. среди данных чисел есть хотя бы два с одинаковым нечетным максимальным делителем (a и b). Т.к. все числа различны, то с точностью до обозначений, будем считать, что a>b. Тогда a в разложении на простые множители содержит двойку в большей степени, чем b. У них одинаковые максимальные нечетные делители, т.е. ab.