|
|
 |
Условие
Из двухсот чисел: 1, 2, 3, ..., 199, 200 выбрали одно число, меньшее 16, и ещё 99 чисел.
Докажите, что среди выбранных чисел найдeтся два таких, одно из которых делится на другое.
Решение
Предположим, что из чисел 1, 2, 3, ..., 199, 200 мы выбрали 100 чисел так, что ни одно из них не делится на другое. Достаточно доказать, что среди
выбранных чисел нет чисел, меньших 16. Рассмотрим наибольшие нечётные делители
всех выбранных чисел. Если наибольшие нечётные делители двух чисел совпадают,
то одно из них делится на другое. Поэтому наибольшие нечётные делители
выбранных чисел – это в точности все числа 1, 3, 5, ..., 199.
В частности, среди выбранных чисел есть числа с наибольшими нечётными делителями 1, 3, 9, 27 и 81. Ни одно из выбранных чисел не делится на другое, поэтому выбранное число с наибольшим нечётным делителем 27 делится на 2, с наибольшим нечётным делителем 9 – на 2², с наибольшим нечётным делителем 3 – на 2³, с наибольшим нечётным делителем 1 – на 24. Следовательно, среди выбранных чисел нет чисел 1, 2, 3, 4, 6, 8, 9 и 12.
Аналогично, рассматривая выбранные числа с наибольшими нечётными делителями 5, 15 и 45, убеждаемся, что среди выбранных чисел нет чисел 5, 10 и 15; рассматривая выбранные числа с наибольшими нечётными делителями 7, 21 и 63, убеждаемся, что нет чисел 7 и 14; рассматривая выбранные числа с наибольшими нечётными делителями 11 и 33, убеждаемся, что нет числа 11; рассматривая выбранные числа с наибольшими нечётными делителями 13 и 39, убеждаемся, что нет числа 13.
