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

質問

正の整数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}も同様です。

回答No.5

Tacosan

「奇数/偶数」でわけるよりも「大きい/小さい」でわける方が直接的だと思うけどね＞#4.

回答No.3

naniwacchi

こんにちわ。
もしかすると「大きい方から」考えると、すんなりできるかもしれません。

いずれにしても、どういう選び方が考えられるかをいくつか試してみた方がいいと思います。
nが 4の倍数のときという制限があるので、n＝ 4と 8の場合を考えて見ます。

i)n＝ 4のとき
1～4の数で条件を満たす集合を考えて見ます。
すると、{ 1, 2, 3 }が要素の数が最大となります。
つまり、f(4)＝ 3です。

ii)n＝ 8のとき
1～8の数で考えることになります。
慎重に調べていくと、{ 1,2,3,5,7 }や { 1,5,6,7,8 }といったものが見つけられます。
実は 2つ目の { 1,5,6,7,8 }に見つけ方のポイントがあります。
というのも、わたしが実際見つけたときの並びは { 8,7,6,5,1 }でした。
同じようにして、{ 7,6,5,4,1 }という並びも見つけられます。

ここから、条件である「mが含まれれば、2mは含まれない。」を逆にとらえて
「2mが含まれれば、mは含まれない。」と考えることにしました。

n＝ 4kのとき
k個ずつの塊が 4つあるように考えます。
{ 1,2,・・・,k }{ k+1,・・・,2k }{ 2k+1,・・・,3k }{ 3k+1,・・・,4k }

すると、先と同じように後ろからみて、後半の { 2k+1,・・・4k }が含まれる場合を考えます。
この集合には、{ 2k+2,2k+4,・・・,4k }という数が含まれています。これらの数を 2で割ると
{ k+1,k+2,・・・,2k }となります。つまり「塊の 2つ目はすべて除外される」ことになります。

あとは、塊の 1つ目にどれだけの候補が残るかということになります。
これは { 1,2,・・・,k }の中で、またさらに上のような 4つの塊ができるかどうかで変わってくるように思います。
もしかすると、kが奇数か偶数かで場合分けすればいいのかもしれません。

後半の 2つの塊には 2k個＝ n/2個の要素が含まれています。
そして、先頭の 1つ目の塊には n/4個の要素が含まれています。
このあたりから、導き出せるのではないでしょうか？

回答No.2

shuu_01

僕にはすごい難しい問題で、本当はよくわかりません

ですので、間違ってそうな気がしますが、ごめんね

まず、f（n/4） と f（n/2） を比べると、

f（n/2） の最大値は f（n/4）＋n/4 です

これは、f（n/4） ＝ 0 かつ
n/4+1、n/4+2、、、n/2 すべて条件を満たしていた時です

n/4+1、n/4+2、、、n/2 すべて条件を満たしているとすると、
それを２倍にした
n/2+2、n/2+4、、、n は条件を満たさないことになります

したがって、この場合、f（n） は増えても
最大 f（n/4）+n/4+n/4 ＝ f（n/4）＋n/2 です

n/4+1、n/4+2、、、n/2 すべて条件を満たしていない
場合も考えられ、その場合、
n/2+1、n/2+2、、、n がすべて条件を満たしていることも
考えられます
その時も f（n）は最大 f（n/4）＋n/2 です

上記は極端な場合ですが、

n/4+1～n/2 の間に １つ条件を満たすものがあれば、
n/2～n の間に少なくとも１つ条件を満たさないものが
あるので、上記以上に f（ｎ） は増えません、、、、

ん～～ん、どっか根本的に考え違えをしてる気がする～～

このような問題を解いたことないので、見当違いの回答を
してた気がします。ごめんなさい m(_o_)ｍ

回答No.1

Tacosan

n を 4 の倍数として, { 1, ..., n/4 } の部分集合でそこの条件を満たす「要素数最大のもの」を M(n/4) とします.

これに n/4+1, ..., n の中からうまく n/2個の要素を追加してその条件を満たす { 1, ..., n } の部分集合を作ってください.