組み合わせ？

質問

N個の要素　a1,a2,a3....,an　から４つを取り出し１つのグループにする、
という動作をN回繰り返し、N個のグループを作る。
このN個のグループから２つのグループを取り出すと、
共通する要素が必ず１つだけ見つかる。(要素とは、最初のa1,a2... のこと)
このときのNの値を求めよ。ただし、取り出し方は無作為。

こんな問題なのですが、どこから手をつけていいのか
さっぱりわかりません。教えてください。

回答No.2

pancho · ベストアンサー

取り敢えずの回答で、一般解を導き出すまでには至ってません。

まず、ｎ≦６の場合は、解が有りません。（自明ですね。）

　　　ｎ＝７の場合は、Ｎ＝２です。（これも自明です。例えば、{a1,a2,a3,a4}{a1,a5,a6,a7}）

ここからは、それまでの解に要素を付け足していくことになりますが、ｎ＝７の解に１個足したｎ＝８では、新しい要素は使うことがでない為に、ｎ＝７と同じ解になります。従って、
　　　ｎ＝８の場合も、Ｎ＝２です。

ｎ＝９では、ｎ＝７で重複していな要素を取り出して、増えた分の要素と組み合わせると解になります。これ以外には有り得ません。例えば、{a1,a2,a3,a4}{a1,a5,a6,a7}{a2,a5,a8,a9}）従って、
　　　ｎ＝９の場合は、Ｎ＝３です。

ｎ＝１０では、ｎ＝９と同じ方法は使えず、ｎ＝７で重複した要素を新しいグループでも共通とする方法が唯一の方法となります。例えば、{a1,a2,a3,a4}{a1,a5,a6,a7}{a1,a8,a9,a10}）従って、
　　　ｎ＝１０の場合も、Ｎ＝３です（？）。

この１つの要素だけが全てのグループに共通するグループの作り方は、この後３個要素が増えるごとに応用できて、一般解になるため、ｎ＝３ｍ＋１（ｍは２以上の整数）となる場合、Ｎ＝ｍとなりますが、これが最大値となる保証はまだありません。

実は、ｎ＝１０の時は、ｎ＝９の時に重複している要素を使わずに新しいグループを作ることができ、Ｎ＝４となる解があります。例えば、{a1,a2,a3,a4}{a1,a5,a6,a7}{a2,a5,a8,a9}{a3,a6,a8,a10}）従って、
　　　ｎ＝１０の場合は、Ｎ＝４になり、前の答えは間違っていたわけです。

さーてこの先が難しいのですが、今はここまで。ペコン！

以上。

回答No.4

pancho

「Ｎ個のグループを作る」ことと、そこから「２個のグループを取り出す」ことのどちらも無作為だとすると、最初の「Ｎ個のグループを作る」ことは、まったく無意味な動作になります。特定のグループに含まれている要素が確定されていないのだから、結局、後の「２個のグループを取り出す」ことは、常に要素全体から２つのグループを作ることに等価ですからね。

Ｎ≧８ならば、互いに要素が重ならないグループを取り出す可能性がありますので、Ｎ≦７の場合のみになります。（題意からＮ≧４でもあります。）

ちなみに、最初の質問どおりに「必ず１つだけ見つかる」のままでしたら、答えは有りません。Ｎがいくつであろうと、無作為であるかぎり、２つのグループの要素が全て一致する可能性は、決して０にはならないからです。

また、最初の回答（＃２）では、ｎとＮが無関係だと勘違いしていました。申し訳ありません。

以上。

お礼

ごめんなさい、もう一度問題を読み直してみます。
お手数をおかけしました。m(__)m

回答No.3

pancho

２番目の回答の補足です。

「Ｎ個のグループを作る方法は作為的にでき」、そこから「２つのグループを取り出すときは無作為で行う」と解釈しましたが、これで良かったでしょうか？

以上。

補足

N個のグループを作る方法も、
グループから２個のグループを取り出すときも「無作為」です。

それから、補足ですが、
「必ず１つだけ」ではなく、「必ず１つは」です。
すみません。

回答No.1

kiku_kiku

えっ！！
無理じゃないですか？

仮に　N＝８　以上だとしたら
a1 a2 a3 a4
a5 a6 a7 a8
の組み合わせが考えられるだろうし・・・
N＝１　～　N＝７でも条件を満たすことはないですから・・・

＞共通する要素が必ず１つだけ見つかる。　
　1つ以上と言うならN ＝４、５，６、７だと思うけど・・・

私が問題を読み違えていたらごめんなさい　ｍ（＿　＿）ｍ