В ряд выписаны все натуральные числа от 1 до 30. Затем некоторые из них вычеркивают таким образом, что оставшиеся в окончательном списке числа подчиняются следующему правилу. Если число $N$ принадлежит списку, то число $2N$ не принадлежит. Какое максимальное количество чисел может остаться?
Все нечетные числа – это неправильный ответ.
Ответ: 20 чисел. Разобьем множество чисел от 1 до 30 на подмножество, каждое из которых содержит нечетное число и числа, полученные умножением этого числа на степени двойки: {1, 2, 4, 8, 16} {3, 6, 12, 24} {5, 10, 20} (7, 14, 28} {9, 18} {11, 22} {13, 26} {15, 30} {17} {19} {21} {23} {25} {27} {29} Мы можем выбирать числа (чтобы оставить в окончательном списке) независимо в каждом подмножестве и можем стремиться оставить как можно больше чисел. Из первого подмножества можем выбрать {1, 4, 16} из второго {3, 12}, из третьего {5, 20}, из четвертого {7, 28} и по одному числу из остальных 11 подмножеств. Всего получится 3 + 2 + 2 + 2 + 11 = 20 чисел
