Числа цвета весны

[Ktina]

Натуральное число $1\le n\le 15$, а также 99 попарно различных натуральных чисел вида $1\le k\le 200$ покрасили в цвет весны.
Доказать, что найдутся два различных числа цвета весны, одно из которых кратно другому.

[Shadow]

Тоест, покрасили 100 чисел, хотя бы одно из них меньше 16? Разбиваем чисел на 100 групп, каждая группа начинает с нечетного числа, осталные $2a_{n-1}$
$\\1,2,4,8,16,32,64,128\\ 3,6,12, 24,48,96,192\\ 5,10,\cdots 160\\ 7,14,28, \cdots\\ 9,18,36, \cdots\\ \cdots\\ 51,102\\ \cdots\\ 65,130\\ \cdots\\ 101\\ \cdots\\ 199$
Понятно что из каждой группы нужно выбрать ровно одно число. Начиная с 101 все "группы" из одного елемента, с 51-го из двух.
Одно число меньше 15, оно нечетным быть не может, т.к найдется нечетное больше 99 на него делящееся. В группах от 51 до 65 должны быть покрашены вторые - четные елементы, по тем же причинам.
Короче, 12 должно быть покрашено, но тогда из группы $9,18,36,72,144$ нечего выбрать.

[Ktina]

Shadow в сообщении #704116 писал(а):

$\\1,2,4,8,16,32,64,128\\ 3,6,12, 24,48,96,192\\ 5,10,\cdots 160\\ 7,14,28, \cdots\\ 9,18,36, \cdots\\ \cdots\\ 51,102\\ \cdots\\ 65,130\\ \cdots\\ 101\\ \cdots\\ 199$

Совершенно верно, разбиваем именно на такие цепочки.
Тогда все нечётные числа от 101 до 199 должны быть покрашены.
Но тогда то число, которое меньше 16, должно быть чётным.

Пусть покрашено число 14.
Тогда из цепочки 21, 42, 84, ... можно покрасить только 21.
А из цепочки 63, 126 -- только 63.
Противоречие.

Пусть покрашено число 10.
Тогда из цепочки 15, 30, 60, ... можно покрасить только 15.
А из цепочки 45, 90, 180 -- только 45.
Противоречие.

Пусть покрашено число 6.
Тогда из цепочки 9, 18, 36, ... можно покрасить только 9.
А из цепочки 27, 54, 108 -- только 27.
Противоречие.

Пусть покрашено число 2.
Тогда из цепочки 3, 6, 12, ... можно покрасить только 3.
А из цепочки 9, 18, 36, ... -- только 9.
Противоречие.

Пусть покрашено число 12.
Тогда из цепочки 9, 18, 36, ... можно покрасить либо 9, либо 18. Но 9 мы покрасить не можем, так как мы уже доказали, что нечётных, меньших 16, быть не должно. Значит, красим 18.
Далее, из цепочки 27, 54, 108 мы не можем покрасить 108, так как уже покрасили 12. Мы не можем покрасить 54, так как уже покрасили 18. Остаётся только 27, красим его.
Теперь из цепочки 81, 162 мы не можем покрасить ни одного числа.
Противоречие.

Пусть покрашено число 8.
Тогда из цепочки 3, 6, 12, 24, ... мы не можем покрасить 3, так как мы уже доказали, что нечётных, меньших 16, быть не должно. Мы не можем покрасить 6 (см. выше пункт "пусть покрашено число 6"), мы не можем покрасить 12 (см. выше пункт "пусть покрашено число 12"). Но мы не можем покрасить и 24 (и далее по цепочке), так как оно делится на 8.
Противоречие.

И наконец, пусть покрашено число 4.
Тогда из цепочки 3, 6, 12, ... мы не можем покрассить ни одного числа (поскольку 12 и выше делятся на 4, а 3 и 6 мы уже доказали).
Противоречие.

Утверждение доказано.

[Shadow]

Ktina в сообщении #704294 писал(а):

Пусть покрашено число 2.

Ну, и число 1 надо рассмотреть для полноты.

[Ktina]

Shadow в сообщении #704304 писал(а):

Ну, и число 1 надо рассмотреть для полноты.

С 1 Апреля!