No.4ベストアンサー
- 回答日時:
問題の意味が分かりにくいときは試行錯誤が必要ですね。
条件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.3
- 回答日時:
こんにちわ。
もしかすると「大きい方から」考えると、すんなりできるかもしれません。
いずれにしても、どういう選び方が考えられるかをいくつか試してみた方がいいと思います。
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
- 回答日時:
僕にはすごい難しい問題で、本当はよくわかりません
ですので、間違ってそうな気がしますが、ごめんね
まず、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 すべて条件を満たしているとすると、
それを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 の間に 1つ条件を満たすものがあれば、
n/2~n の間に少なくとも1つ条件を満たさないものが
あるので、上記以上に f(n) は増えません、、、、
ん~~ん、どっか根本的に考え違えをしてる気がする~~
このような問題を解いたことないので、見当違いの回答を
してた気がします。ごめんなさい m(_o_)m
No.1
- 回答日時:
n を 4 の倍数として, { 1, ..., n/4 } の部分集合でそこの条件を満たす「要素数最大のもの」を M(n/4) とします.
これに n/4+1, ..., n の中からうまく n/2個の要素を追加してその条件を満たす { 1, ..., n } の部分集合を作ってください.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 問題の解説と回答をお願いします┏● 2つの集合A={2,5,6,7,8}とB={5,7,8}について 1 2022/04/27 23:12
- 数学 問題の解説と回答をお願いします !! 2つの集合A={1,2,3,4,6,8,9,10}とB={2, 1 2022/04/27 23:19
- 数学 順序集合における「反射律」の役割について 9 2022/05/09 23:01
- 数学 急用で出れなかった授業のレポートの回答を解説して欲しいです !! (問)次の集合の要素の個数 n(A 1 2022/04/27 21:20
- 高校 急用で出れなかった授業のレポートの回答を解説して欲しいです !! (問)次の集合の要素の個数 n(A 1 2022/04/27 22:41
- 数学 代数学のわからない問題を教えて頂きたいです。 つぎのn次正方行列の集合Hはn次一般線形群GL(n,R 5 2022/11/19 20:47
- 数学 分母を810,分子を1から809までの整数とする分数の集合{1/810,2/810,…,809/81 3 2022/06/18 10:29
- 大学受験 整数問題 Nを正の整数とする。 N+18がN+2の倍数となるようなNの値の個数を求めたい。 解説に、 1 2022/08/13 12:25
- 数学 【 数A 集合の要素の個数 】 問題 100から200までの整数のうち, 5の倍数であるが,3の倍数 5 2022/07/18 13:33
- 数学 【数A 集合の要素の個数】 問題 100から200までの整数のうち, 3の倍数でない整数は何個あるか 3 2022/07/18 13:07
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
∈と⊂の違いは何ですか?
-
私がばかなのか?
-
集積点が、まったく分かりませ...
-
数字は存在するのか
-
赤チャートの集合の問題です。...
-
大学数学 任意の自然数nに対し...
-
R\\{0} って、0を除く実数って...
-
数学の集合で閉じているの意味...
-
0以外の実数全体のどれかになる...
-
この黄線で、囲んだ部分の縦線...
-
凸集合
-
有理数÷有理数は絶対有理数なん...
-
順序集合について…
-
巾集合
-
Rの半開区間(0,1]と開区間(0,1)...
-
(1)PまたはQを通る道順 (2)図中...
-
真部分集合に関する質問
-
こういう考え方は数学でどう扱...
-
集合族の定義で、集合の集合と...
-
部分が全体に等しいのが無限で...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
∈と⊂の違いは何ですか?
-
集積点が、まったく分かりませ...
-
要素と、部分集合の違いを教え...
-
数学で、数字の上にある横線の意味
-
数学でのセミコロンについて
-
部分が全体に等しいのが無限で...
-
数字の上のバー
-
数字は存在するのか
-
R\\{0} って、0を除く実数って...
-
ACCESSのSQL
-
高1数学
-
(1)PまたはQを通る道順 (2)図中...
-
1から100までの自然数で、3,4,5...
-
6以下の自然数全体の集合の要素...
-
空集合のべき集合
-
∈ と ⊂ のはっきりとした違い
-
Rの半開区間(0,1]と開区間(0,1)...
-
何故線型空間はあっても、非線...
-
集合
-
高校1年の数学Aです。 この、ピ...
おすすめ情報