プロが教えるわが家の防犯対策術!

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

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

A 回答 (4件)

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



まず、n≦6の場合は、解が有りません。(自明ですね。)

   n=7の場合は、N=2です。(これも自明です。例えば、{a1,a2,a3,a4}{a1,a5,a6,a7})

ここからは、それまでの解に要素を付け足していくことになりますが、n=7の解に1個足したn=8では、新しい要素は使うことがでない為に、n=7と同じ解になります。従って、
   n=8の場合も、N=2です。

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

n=10では、n=9と同じ方法は使えず、n=7で重複した要素を新しいグループでも共通とする方法が唯一の方法となります。例えば、{a1,a2,a3,a4}{a1,a5,a6,a7}{a1,a8,a9,a10})従って、
   n=10の場合も、N=3です(?)。

この1つの要素だけが全てのグループに共通するグループの作り方は、この後3個要素が増えるごとに応用できて、一般解になるため、n=3m+1(mは2以上の整数)となる場合、N=mとなりますが、これが最大値となる保証はまだありません。

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

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

以上。
    • good
    • 0

「N個のグループを作る」ことと、そこから「2個のグループを取り出す」ことのどちらも無作為だとすると、最初の「N個のグループを作る」ことは、まったく無意味な動作になります。

特定のグループに含まれている要素が確定されていないのだから、結局、後の「2個のグループを取り出す」ことは、常に要素全体から2つのグループを作ることに等価ですからね。

N≧8ならば、互いに要素が重ならないグループを取り出す可能性がありますので、N≦7の場合のみになります。(題意からN≧4でもあります。)

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

また、最初の回答(#2)では、nとNが無関係だと勘違いしていました。申し訳ありません。

以上。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/12/06 08:32

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



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

以上。

この回答への補足

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

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

補足日時:2001/12/05 15:23
    • good
    • 0

えっ!!


無理じゃないですか?

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

>共通する要素が必ず1つだけ見つかる。 
 1つ以上と言うならN =4、5,6、7だと思うけど・・・

私が問題を読み違えていたらごめんなさい m(_ _)m
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!