OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

組み合わせ?

  • 困ってます
  • 質問No.180084
  • 閲覧数45
  • ありがとう数1
  • 気になる数0
  • 回答数4
  • コメント数0

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

こんな問題なのですが、どこから手をつけていいのか
さっぱりわかりません。教えてください。
通報する
  • 回答数4
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル12

ベストアンサー率 35% (302/848)

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

まず、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になり、前の答えは間違っていたわけです。

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

以上。
-PR-
-PR-

その他の回答 (全3件)

  • 回答No.1
レベル8

ベストアンサー率 46% (12/26)

えっ!! 無理じゃないですか? 仮に N=8 以上だとしたら a1 a2 a3 a4 a5 a6 a7 a8 の組み合わせが考えられるだろうし・・・ N=1 ~ N=7でも条件を満たすことはないですから・・・ >共通する要素が必ず1つだけ見つかる。   1つ以上と言うならN =4、5,6、7だと思うけど・・・ 私が問題を読み違えていたらごめんなさい m(_ _)m
えっ!!
無理じゃないですか?

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

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

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

  • 回答No.3
レベル12

ベストアンサー率 35% (302/848)

2番目の回答の補足です。 「N個のグループを作る方法は作為的にでき」、そこから「2つのグループを取り出すときは無作為で行う」と解釈しましたが、これで良かったでしょうか? 以上。 ...続きを読む
2番目の回答の補足です。

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

以上。
補足コメント
noname#5824

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

それから、補足ですが、
「必ず1つだけ」ではなく、「必ず1つは」です。
すみません。
投稿日時 - 2001-12-05 15:23:52
  • 回答No.4
レベル12

ベストアンサー率 35% (302/848)

「N個のグループを作る」ことと、そこから「2個のグループを取り出す」ことのどちらも無作為だとすると、最初の「N個のグループを作る」ことは、まったく無意味な動作になります。特定のグループに含まれている要素が確定されていないのだから、結局、後の「2個のグループを取り出す」ことは、常に要素全体から2つのグループを作ることに等価ですからね。 N≧8ならば、互いに要素が重ならないグループを取り出す可能性があり ...続きを読む
「N個のグループを作る」ことと、そこから「2個のグループを取り出す」ことのどちらも無作為だとすると、最初の「N個のグループを作る」ことは、まったく無意味な動作になります。特定のグループに含まれている要素が確定されていないのだから、結局、後の「2個のグループを取り出す」ことは、常に要素全体から2つのグループを作ることに等価ですからね。

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

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

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

以上。
お礼コメント
noname#5824

ごめんなさい、もう一度問題を読み直してみます。
お手数をおかけしました。m(__)m
投稿日時 - 2001-12-06 08:32:24
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ