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

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

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

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

A 回答 (8件)

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

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

チームに所属している人の集合と、所属していない人の集合を考えます。例えば、3人のとき、#5さんの例を使うと、
所属している人の集合……{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)個のチームを作れることを示すことはできます。
    • good
    • 0
この回答へのお礼

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

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

#6です。

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

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

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

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名以上になるので、共通する人が少なくとも1人はいます。したがって条件イも満たしています。

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

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


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

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

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

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

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

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



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

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

ここにもう1人Bが増えた場合、Bが加わるか否かで、2つのチームになります。
{A}
{A,B}

次にもう1人Cが増えた場合、同様に既存のチームがそれぞれ2つのチームになります。
{A}{A,C}
{A,B}{A,B,C}

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

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

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

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

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

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

>bgoma氏



A~Cの3人いるとする。

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

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

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

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

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

この回答への補足

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

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

補足日時:2005/04/01 15:39
    • good
    • 0

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



-----
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通り増えた。
    • good
    • 0

A~Cの3人がいる。


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

この回答への補足

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

補足日時:2005/04/01 15:09
    • good
    • 0

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


人気Q&Aランキング

おすすめ情報