一番でかい数出した奴が優勝

このエントリーをはてなブックマークに追加
話は大幅に変わるんだけど(汗)、545などに書いてある委員会問題は、つまりこういうことではないでしょうか?

例えば3人の人がいたとして、彼らの属し方がおのおの異なる委員会を考える。
すなわち、3人のうち一人が属している委員会3つ、二人が属している委員会3つ、
3人全員が属する委員会、そして3人とも属していない委員会の8つである。

次に、この8つの委員会からできうるすべての「委員会のペア」を挙げてみる。
すると、(8*7)/2=28 のペアが考えられる。そしてこれらのペアを
二つのグループのどちらか一方に振り分けていく。

このとき、振り分け方がどのようなものであっても、
次の条件を満たす4つの委員会が常に1組以上存在するか調べる。

 1.それらの委員会からできるすべてのペア(6つ)が同じグループに属している
 2.各人がそれらのうちの偶数個の委員会の属している

委員会が8つの場合、条件1を確実につぶせる振り分け方が考えられる。
つまり3人では人数が足りないと言うことになる。

それでは最低何人そろえば良いのか? その答えこそがグラハム数なのである。






(でも、n人で成り立つからと言って、m>n なm人で成り立つものなのでしょうか・・・?)