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

Автор темы koh 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеМатематики, программисты, репетиторов (платформа SapioX)28.01.2021 12:47
ОбъявлениеПостдок позиция по математике в Гетеборге (Швеция)10.09.2021 19:11
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 чисел

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

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