Максимальное по мощности подмножество

[devgen]

Есть множество $A=\{1,2,\dots,256\}$. Надо выбрать максимально по мощности подмножество $A'$, так, что в нем нет элементов $x,y$, таких что $x=2y$.

Сначала подумал на числа каталана, но как это их никак сюда. Потом подумал, что нужно воспользоваться тем, что это множество с максимальной мощностью, значит как только мы добавим в него еще один любой элемент $z$ из $A \setminus A'$, то найдется такой $x\in A'$, что $z=2x$ или $x=2z$. Наверное, это бы было как-то действенно, если бы я представлял себе, что такое $A \setminus A'$, но я не могу охарактеризовать, что это за множество.

[Cash]

Найдите подмножество с этим свойством из 128 элементов и докажите, что из 129 таких нет (принцип Дирихле).

[provincialka]

Я тоже сначала так подумала, но 129 - можно! Например, $\{1,129,130, ..., 256\}$. И больше можно.

[Cash]

И действительно, просчитался, не стоит такие вещи в уме прикидывать

-- Пн мар 31, 2014 15:15:53 --

Больше 172 нельзя. Но пример у меня есть только со 171.

[ИСН]

А и 172 нельзя.

[Cash]

Делаем примерно так: числа $1..256$ надо разбить на пары $(x,2x)$
У меня получилось выделить 85 непересекающихся пар (если опять не обсчитался). Соответственно из $256-85+1=172$ чисел два числа окажутся в одной паре. И осталось найти пример со 171 числом.

[ИСН]

Не надо пары. Надо цепочки из чисел, последовательно отличающихся в 2 раза. Если в цепочке одно или два числа, то можно взять одно. Если 3 или 4 - то 2. Если 5 или 6 - то 3. И так далее.
Какие есть цепочки и сколько - посчитать легко.

[Jim_Hawkins]

Моё решение.
Будем строить $A'$.
Заметим сразу, что все нечётные элементы множества $A$ содержится в $A'$.
То есть

$$A_1 = \{ 2k-1 \ | \ k = 1, \ \ldots \ , 128\} \subset A'.$$

Ясно, что если элемент $a \in A'$, то и $4a \in A'$ (при условии $4a \leqslant 256$). Получаем

$$ \begin{aligned} & A_2 = \{ 4 \cdot (2k-1) \ | \ k = 1, \ \ldots \ , 32 \} \subset A', \\ & A_3 = \{ 16 \cdot (2k-1) \ | \ k = 1, \ \ldots \ , 8 \} \subset A', \\ & A_4 = \{ 64 \cdot (2k-1) \ | \ k = 1, \ 2 \} \subset A', \\ & A_5 = \{ 256 \cdot (2k-1) \ | \ k = 1 \} \subset A', \\ \end{aligned} $$

Множества $A_i$ попарно не пересекаются, значит,

$$ A' = \bigcup_{i=1}^5 A_i \quad \text{и} \quad |A'| = 128+32+8+2+1 = 171. $$

Ответ: $171$.