構成できるチーム数

ある部署では、１年間通じて活動するプロジェクトチーム（以下、チーム）をいくつか構成することになっているが、これらのチームは次のア、イ、ウの要件に従って構成されている。
ア　チームごとの多様性を発揮させるため、構成メンバーが全員同じチームは作らない。
イ　チーム間の情報共有のため、どの二つのチームの構成メンバーを見ても、必ず共通する人が少なくとも１人はいる。
ウ　チームは１名で構成してもよい。
この部署には昨年８名が所属していたが、今年は１名増えて９名となった。このとき、今年構成できるチームの数は昨年よりいくつ増えたか。

答えは次のようになっています。

昨年の８名の中に、どのチームにも共通する人が少なくとも１人（この人は、結局どのチームにも所属していることになる）はいることから、他の７名について考えると、どの人もチームの構成メンバーに入るか入らないかで２通りの選択肢があるので、全部で2^7=12通りのチームができることになる。
今年は１名増えて９名になれば、同様にして2^8=256通りのチームができるから、昨年に比べて、256-128=128通り増えたことになる。

この説明の１文目で、「どのチームにも所属している」というのが理解できないでおります。イの条件から来ている結論だと思うのですが、どうしてどのチームにも所属していることがいえるのでしょうか。

No.6 ベストアンサー 回答者： Naoki_M 回答日時： 2005/04/02 12:28

すでにみなさんご指摘の通りですが、「どのチームにも所属している人がいる」というのは誤りです。

おそらく質問文の答えを書いた人は、必要条件と十分条件を混同してしまったのでしょう。答えの数字は合っています。長くなりますが、＃２さんとは別の解答を投稿します。

チームに所属している人の集合と、所属していない人の集合を考えます。例えば、3人のとき、＃５さんの例を使うと、
所属している人の集合……{A,B,C},{A,B},{A,C},{B,C}
所属していない人の集合……{},{C},{B},{A}
です。

これを使って、条件を満たしてつくれるチーム数が最大2^(n-1)であることを証明します。そこで、「条件を満たしながら、2^(n-1)より多くチームを作れた」と仮定します。

このとき、
（所属している人の集合の数）＋（所属していない人の集合の数
＝（所属している人の集合の数）×2
>2^n
です。0人で構成されるチームも含めると、n人で構成することのできるチーム数は2^nですから、次の(i)(ii)のどちらかが成立します。

(i)所属している人の集合の中に同じものが存在する（所属していない人の集合の中に同じものが存在する）
これは条件アに反しています。

(ii)参加する人の集合と参加しない人の集合の中に同じものが存在する
これは条件イに反しています。

(i),(ii)より、2^(n-1)より多くチームを作れたという仮定は誤りです。したがって、作れるチーム数は最大でも2^(n-1)です。

次に、「条件を満たしながら、2^(n-1)個のチームを作れる」ということを示す必要があります。考え方はいろいろありますが、例えば「どのチームにも所属している人がいる」と仮定すると、2^(n-1)個のチームを作れることを容易に示すことができます。あとの計算は質問文の通りです。なお、「どのチームにも所属している人はいない」としても、2^(n-1)個のチームを作れることを示すことはできます。

この回答へのお礼

皆さん回答ありがとうございます。
いろいろと落とし穴のある問題だと思いましたが、
＃６さんの説明が一番厳密な説明だと思います。
ただ、全員の説明を読まなければ＃６さんの説明も僕は理解できなかったと思うので、回答者全員に感謝いたします。

お礼日時：2005/04/02 21:15

No.8 回答者： Naoki_M 回答日時： 2005/04/02 19:09

＃６です。

私の回答の中のnについて説明し忘れていました。nは部署の人数です。

「どのチームにも所属している人がいる」「特定の1名が必ず全てのチームに所属している」は必ずしも成り立ちません。したがって、質問文の中の答え、＃３さんの回答、＃７さんの回答は残念ながら間違っています。

「どのチームにも所属している人がいるならば、チームの数を最大にすることができる」なら成り立ちますが、「チームの数が最大ならばどのチームにも所属している人がいる」は必ずしも成り立ちません。

9名のとき、「特定の1名が全てのチームに所属しているということはない」としても、256個のチームを作ることはできます。

9名の中から9名を選んでできるチーム（チーム数は9C9=1）
9名の中から8名を選んでできるチーム（チーム数は9C8=9）
9名の中から7名を選んでできるチーム（チーム数は9C7=36）
9名の中から6名を選んでできるチーム（チーム数は9C6=84）
9名の中から5名を選んでできるチーム（チーム数は9C5=126）

これらのチーム全てを考えます。チーム数の合計は1+9+36+84+126=256です。

この256チームは条件アイウを全て満たしています。条件アウを満たしているのは明らかです。また、どの二つのチームを選んでも、延べ人数は10名以上になるので、共通する人が少なくとも１人はいます。したがって条件イも満たしています。

しかし、この256チームの中には、「どのチームにも所属している人」はいません。例えば、9名の中から8名を選んでできる9つのチームの中には、9人それぞれについて、所属していないチームが1つずつあります。

No.7 回答者： sunasearch 回答日時： 2005/04/02 14:32

n個のチームがあったときに、任意の２チームの選び方は、

nC2 = n(n-1)/2 通りあります。

イの条件を満たすには、
このおのおののチームをつなぐパイプ役になる人を、
８人の中から必ず誰かを選ぶ必要があります。

パイプ役になった人は、その選ばれたチームに所属しないといけないという「制約」が与えられますから、それだけチームの種類数を制限することになります。

ですから、パイプ役の人が少ないほど、できるチームの数が多くなることになります。

＃３さんのおっしゃられるように、
できるチームの数を最大として考えるならば、
だれか１人がすべてのチームに属しているという状態になります。　

No.5 回答者： ZeusSeesSuez 回答日時： 2005/04/01 18:43

なかなかややこしいですが、整理してみます。

ANo.2に書かれていることを具体的に確認すると…

所属が１名(Ａ)の場合明らかに１チーム
{Ａ}。

ここにもう１人Ｂが増えた場合、Ｂが加わるか否かで、２つのチームになります。
{Ａ}
{Ａ，Ｂ}

次にもう１人Ｃが増えた場合、同様に既存のチームがそれぞれ２つのチームになります。
{Ａ}{Ａ，Ｃ}
{Ａ，Ｂ}{Ａ，Ｂ，Ｃ}

以下、１人増える毎にチーム数は２倍になっていきます。

で、この場合はＡがどのチームにも所属していることになります。

つまり、ANo.2は、「どのチームにも所属している人がいる」ことを示しています。

ところがです。ANo.1にあるように、３人のとき、上記以外のチーム構成が存在するのです。
{Ａ}{Ａ，Ｂ}{Ａ，Ｃ}{Ａ，Ｂ，Ｃ}でなく、
{Ａ，Ｂ}{Ｂ，Ｃ}{Ａ，Ｃ}{Ａ，Ｂ，Ｃ}でも条件を満たします。
(ちなみにANo.4で示されている{Ａ}{Ａ，Ｂ}{Ｂ，Ｃ}{Ａ，Ｃ}は、
{Ａ}と{Ｂ，Ｃ}に共通する人がいないのでだめです。残念)
以降１人ずつ増やしてゆくと、最初の場合と同様に２倍になってゆきますが、すべてのチームに所属する人はいません。

結論としては、
３人以上の場合は、どのチームにも所属している人がいるとは必ずしも言えない、ということです。

ちなみに、ウの条件を「１名で構成されるチームが必ず存在する」とすれば、
どのチームにも所属する人が必ず１人いることになります。

No.4 回答者： minds777 回答日時： 2005/04/01 15:53

>bgoma氏

Ａ～Ｃの3人いるとする。
Ａ
ＡＢ
ＢＣ
ＡＣ
の4つのチームそれぞれについて新たにn-3人が所属して新たなチームを作ります。その場合作れるチーム数は4*2^(n-3)=2^(n-1)個。これは現在論じられている範囲で、n人で構成できる最大のチーム数に等しく、ア、イ、ウの条件を全て満たす。しかし、全てのチームに属する人間は存在しない。

よってそんなことは有りません。

---
実はＡさんが属さないチームを作ることは、補集合を考えるとＡさんが属するチームを作ることと同じです。よってＡさんが全てのチームに属すると考えても問題はないのですが、解答に書くにはそのことについて言及する必要があります。

No.3 回答者： bgoma 回答日時： 2005/04/01 15:14

この質問は、決められた人数で構成できる最大のチーム数を聞いています。

チーム数が多いと、特定の１名を必ず全てのチームに所属させないと、条件イに反することになってしまいます。

この回答への補足

＞チーム数が多いと、特定の１名を必ず全てのチームに所属させないと、条件イに反することになってしまいます。

え？それはどうしてなんですか？#1さんの回答を見ても、そのようには思えないのですが。

補足日時：2005/04/01 15:39

No.2 回答者： minds777 回答日時： 2005/04/01 15:14

ついでに正しいと思われる答えを。

-----
n人いて作れるチーム数をAnとする。

まず、明らかにA1=1。
次にk人のときAk=2^(k-1)であったと仮定し、k+1人の場合を考える。この場合、k人で作られるAk個のチームそれぞれについて、k+1人目が属するか否かで、2つの新たなチームを作ることが出来る。また、これ以外に条件を満たす新たなチームは作れない。
よってA_(k+1) = 2*Ak = 2^k = 2^{(k+1)-1}
以上からAn=2^(n-1)



ここで、A9-A8 = 2^(9-1) - 2^(8-1) = 128
よって128通り増えた。

No.1 回答者： minds777 回答日時： 2005/04/01 14:31

Ａ～Ｃの３人がいる。

ＡＢ、ＢＣ、ＡＣの３チームを作った。
これはア、イ、ウ全ての条件に適する。
しかし全てのチームに属する人物は存在しない。
よって[答え]とやらを作った人は馬鹿です。

この回答への補足

私もそう思ったんですよね。
結果はあってるんですかね。
任意の２チームをとったとき、誰か一人は共通させねばならないから・・・。

補足日時：2005/04/01 15:09