Подмножество

[wpoms.]

Может ли множество `{1, 2, 3,..., 3000}` содержать подмножество из `2000` элементов, таких, что ни один из них не является удвоенным значением другого?

@темы: Множества

Comments

[Trotil]

У меня получилось выбрать 2124 элемента с указанным условием. Кто больше?

[Груша Вильямс]

У меня пока все нечетные с 3 плюс все те которые степени двойки с нечетными показателями...То есть 1499+6=1505, пойду думать дальше.

[Груша Вильямс]

Trotil, 2247, вроде бы ещё можно больше...
`3,5,7,9,11,...,2999` — `1499` штук
`2,8,32,128,512,2048` — `6` штук
`4*1,4*2,4*3,...,4*750` из этого набора уберем этот `4*1,4*2,4*4,...,4*512` — `750-8=742` штуки
ещё надо кратные `16,64,256` перебрать-посмотреть...

[Trotil]

Оказывается, я неверно просуммировал )
1,3,...,2999 = 1500 штук.
1504,1508,...,3000 = 500 штук
376, ..., 748 = 93 штуки
96,...,184 = 22 штуки
28,...,44 = 4 штуки
4,12 = 2 штуки.
--------------------------
2123 элемента.

[Trotil]

ещё надо кратные `16,64,256` перебрать-посмотреть...

А еще одно число из пары 12,24... и.т.д.

[Груша Вильямс]

Вот вроде бы все учёл

Итого: `(11-4)+(46-6)+(187-8)+(750-10)+1499+6=2471`