Вычеркивание чисел

Автор темы koh 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеPostdoc: Stochastics and algorithmics behind network problems (Netherlands)08.10.2021 08:36
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
24.04.2022 22:57
Вычеркивание чисел
Условие

В ряд выписаны все натуральные числа от 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 чисел

Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти