赤チャートの集合の問題です。解説お願いします。

質問

正の整数nに対して、集合{1,2,...,n}の部分集合Mで条件m∈Mならば2m∉M
を満たすものを考える。このような集合Mに対してMの要素の個数の取り得る
最大値をf（n）と表すとすると、nが4の倍数であるとき、
f（n）≧n/2 ＋f（n/4）が成り立つことを示せ。
という問題がまったくわかりません。解説お願いします。

回答No.4

englishquestion · ベストアンサー

問題の意味が分かりにくいときは試行錯誤が必要ですね。

条件m∈Mならば2m∉Mを考えると、ある要素の2倍の数が入ってはならず、
逆に言えば、ある要素の半分の数も入ってはならないとうことです。
その「半分の数」から見れば、その要素が「2倍の数」になるからです。

n＝8のときを考えます。
M={1,2,3,4,5,6,7,8}
まず、この中から安心して選べるものを探します。
それは、大きさで2つに分けた半分の集合{5,6,7,8}の中の奇数です。
なぜならば、それは、自分の半分の数は整数でないですし、
自分の倍の数は、大きくなってしまって、Mの中にないからです。
これで{5,7}が選べます。
ここからは試行錯誤ですが、
・このまま奇数を全部選ぶ
・このまま上半分を全部選ぶ
のどちらかを考えます。
なぜならば、f（n）≧n/2 ＋f（n/4）という式の
n/2がMの半分の要素を選ぶということを言っているように思え、
そして{5,7}を含んで半分（4つ）選ぶとなると、
この2通りくらいしか思い付かなかったからです。

結論から言えば、「まず奇数を全部選ぶ」ということでうまくいきます。

奇数の要素数はn/2です。
選んだあと残るのは、偶数の集合{2,4,6,8}　ですが
このうち、奇数の倍になっているもの、
2と6は選ぶことができません。
そして、4と8、すなわち4の倍数となっているものは
奇数の倍になる心配が完全にありませんので、この検討をします。
4と8 これは同時には選べません。
どちらかしかMには入れませんし、また一方ならばMに入れることが出来ます。
この両者の関係は、それぞれ、4で割った時の、{1,2}の要素の関係に等しいです。
したがって、{1,3,5,7,8}（8の代わりに4でもいいです）が条件に合うものとして
考えることができ、
f（n）≧n/2 ＋f（n/4）でn=8とした式、
f（8）≧8/2 ＋f（8/4）= 4 ＋f（2）= 5
が成り立っていることが分かります。

全部奇数をまず選び、その後、4の倍数の数同士で
再度相互の関係を考えればよいのです。
それを表したのが、
f（n）≧n/2 ＋f（n/4）
です。

nが他の4の倍数であって、まず奇数を全部選び（n/2個）、
あと、4の倍数同士で再度、条件を考えなおす（f(n/4)個）ことをすれば、
よいことが分かります。

他の選び方でもってたくさん選べる可能性があるので　＞ がついていますが、
少なくとも、n/2 ＋f（n/4）個の要素選び出すことができることは間違いありません。

※質問者さんへ
赤チャートには解答が載っているわけですよね？
その解答のどこがわからないのか具体的に書いていただいたほうが
的確な説明ができるかと思います。

※ #3さんへ
n＝4のときは{1,2,3}が選べるとおっしゃっていますが、1と2がぶつかっています。
n＝8の{1,2,3,5,7}も同様です。