2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Максимальное по мощности подмножество
Сообщение31.03.2014, 13:56 
Найдите подмножество с этим свойством из 128 элементов и докажите, что из 129 таких нет (принцип Дирихле).

 
 
 
 Re: Максимальное по мощности подмножество
Сообщение31.03.2014, 13:58 
Аватара пользователя
Я тоже сначала так подумала, но 129 - можно! Например, $\{1,129,130, ..., 256\}$. И больше можно.

 
 
 
 Re: Максимальное по мощности подмножество
Сообщение31.03.2014, 14:02 
И действительно, просчитался, не стоит такие вещи в уме прикидывать

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

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

 
 
 
 Re: Максимальное по мощности подмножество
Сообщение31.03.2014, 14:58 
Аватара пользователя
А и 172 нельзя.

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

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

 
 
 
 Re: Максимальное по мощности подмножество
Сообщение07.02.2017, 07:57 
Моё решение.
Будем строить $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$.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group