鳩ノ巣原理 
高校で習う論証法としては、「背理法」や「数学的帰納法」が有名である。「平方根２
が無理
数である」ことを示すのに、背理法が使われるが、大学入試における、その他もろもろの問
題においても、背理法が登場する頻度は高い。また、自然数 ｎ に関する命題の証明には、
数学的帰納法が活躍する。「自然数 ｎ に対して、２n＞ｎ 」を示す場合、直接的な証明も可
能であるが、数学的帰納法による証明の方が簡明である。
結論を否定して、矛盾を導くという背理法の証明方法は、新しい数学の定理を創造するの
に有効である。いくつか具体的な事例を計算して結論の予想を立て、それを証明する場合、
背理法が主に使われる。大学院時代、同じ研究室にいらした、群論を専門とする方に論文
を見せてもらう機会があったが、ほとんど背理法一色であった。それだけ、背理法は数学的
な論証において、強力な武器となりうる。
この「背理法」や「数学的帰納法」に匹敵すると思われる、論証の武器 ：「鳩ノ巣原理」は、
なぜかしら高校で教えられることはない。しかし、数学オリンピックの必須アイテムであるこ
とを考えると、世界の標準的な論証法と考えるべきだろう。鳩ノ巣原理は、存在定理を証明
するときに有効である。
鳩ノ巣原理自体は、とても当たり前のことを主張する。
鳩ノ巣原理（・・・ディリクレの引き出し論法、部屋割り論法ともいわれる）
ｎ 個の巣穴に ｎ＋１ 羽の鳩を入れる場合、
必ずどれかの巣穴は、２ 羽以上
これを一般化して、
ｎ 個の巣穴に ｍ 羽の鳩を入れる場合、ｍ＞ｋｎ ならば、
必ずどれかの巣穴は、ｋ＋１ 羽以上
|
 |
「たくさんあるものの中で、２つ（以上）は同じ」ことを示したりする場合、鳩ノ巣原理がよく
用いられる。次の問題に対して、この鳩ノ巣原理を応用してみよう。
問題 実数係数の３次方程式が次の性質を持つとする。
α が解ならば、その平方 α2 も解になる
このとき、この性質を持つ３次方程式の解の絶対値は、０ または １ である。
（解） 今 α が解ならば、α2、α4、α8 も解になる。ところが、３次方程式は、３個の解しか
もたないので、α、α2、α4、α8 のうち相等しいものが存在する。（鳩ノ巣原理）
そこで、ある ｍ、ｎ に対して、αｍ＝αｎ （ｍ＞ｎ）とすると、
αｎ（αｍ−ｎ−１）＝０
から、｜α｜ｎ＝０、｜α｜ｍ−ｎ＝１ となり、｜α｜＝０、１ が成り立つ。（終）
この問題からも分かるように、何が鳩ノ巣で、何が鳩かを把握することが、この論法のキ
ーポイントである。上記問題では、３個の解が鳩ノ巣で、４つの数 α、α2、α4、α8 が鳩に
相当する。
鳩ノ巣原理は、その単純さから、一般の人にとっても納得されやすい原理であるが、実際
に、問題解決に利用しようとする場合、相当の熟練を要する。このページでは、鳩ノ巣原理
を利用する問題をいくつか提示して、その適用の仕方を見ていこう。これらの例題をマスタ
ーすれば、無意識の内に「鳩ノ巣原理」が使えるようになるだろう。
例題１ 分数を小数に直す場合、有限小数か、循環小数である。これは、どうしてか？
（解） 分子を分母で割り算したとき、割り切れれば、有限小数である。割り切れず、永
遠に割り算が繰り返される場合に、循環小数ができる。
実際に、分母 ｎ で割ったとき、その余りの可能性は、１、２、３、・・・、ｎ−１
の
ｎ−１ 個ある。（これが、鳩ノ巣）
今、ｎ 回割り算を繰り返して、余りが、ｎ 個得られたとする。（これが、鳩）
このとき、鳩ノ巣原理により、この余りのうち、少なくとも２つは同じ数である。
よって、その同じ数に対応するところから、小数は循環する。（終）
例題２ １辺が ４ の正方形の内部および辺上に、９つの点をとる。このうちの３点を結ん
で三角形を作るとき、すくなくとも一つの三角形の面積は、２ 以下である。
（解） 与えられた正方形の各辺の中点を結んで、４つの合同な正方形に分割する。（こ
れが、鳩ノ巣） いま、９つの点（これが、鳩）があるので、鳩ノ巣原理により、
９＞２×４ から、少なくとも一つの三角形の内部および辺上に、２＋１＝３
個以上
の点がある。このうちの３点で作られる三角形の面積は、２ 以下である。（終）
（ものの本によると、このような三角形は、少なくとも２個あるらしい！）
例題３ １辺が ２ の正三角形の内部および辺上に、５つの点をとる。このとき、２点間の
距離が １ 以下であるような２点が存在する。
（解） 与えられた正三角形の各辺の中点を結んで、４つの合同な正三角形に分割する。
（これが、鳩ノ巣） いま、５つの点（これが、鳩）があるので、鳩ノ巣原理により、ど
れか１つの正三角形の内部および辺上に、２つ以上の点がある。このうちの２点を
結んで得られる線分の長さは、１ （正三角形の一辺の長さ）以下である。（終）
例題４ ３で割って １ 余る数の数列： １，４，７，・・・，９７，１００ を考える。この３４個の数
から相異なる ２０ 個の数をどのように選んでも必ず、その ２０ 個の中に、２つの相
異なる数で、和が、１０４ となるものが存在する。
（解） 和が、１０４ となる数の組合せは、
４＆１００、７＆９７、１１＆９４、・・・、４９＆５５ の１６
通りある。この各場合に使わ
れていない数は、１ と ５２ である。そこで、次の １８ 通りの場合を考える。
４＆１００、７＆９７、１１＆９４、・・・、４９＆５５、１、５２ （これが、鳩ノ巣）
今、相異なる ２０ 個の数を任意に選ぶ。（これが、鳩）
このとき、鳩ノ巣原理により、２つの数とも選ばれている対 Ａ＆Ｂ
が存在して、
Ａ＋B＝１０４ である。（終）
例題５ １ から １９９９ までの１０００個の奇数がある。この中から、 ５０１個の奇数をどの
ように選んでも必ず、その ５０１ 個の中に、２つの相異なる数で、和が、２０００
とな
るものが存在する。
（解） 和が、２０００ となる数の組合せは、
１＆１９９９、３＆１９９７、５＆１９９５、・・・、９９９＆１００１ の５００
通りある。（これ
が、鳩ノ巣） 今、相異なる ５０１ 個の奇数を任意に選ぶ。（これが、鳩）
このとき、鳩ノ巣原理により、２つの数とも選ばれている対 Ａ＆Ｂ
が存在して、
Ａ＋B＝２０００ である。（終）
例題６ 任意に与えられた相異なる４つの整数から適当に２つ選ぶと、その差は、３ の倍
数になる。
（解） ４つの整数を ３ で割った余りを、それぞれ ｐ、ｑ、ｒ、ｓ とおく。（これが、鳩）
ところで、整数を ３ で割った余りは、０、１、２ のいずれか。（これが、鳩ノ巣）
よって、鳩ノ巣原理により、ｐ、ｑ、ｒ、ｓ のうちに少なくとも２つ相等しいものがある。
そのうちの２つについて差をとれば、その差は、３ の倍数になる。（終）
上記の例題６は、次のように一般化される。
例題６’ 相異なる ｎ＋１ 個の整数から適当に２つ選ぶと、その差が、ｎの倍数になるもの
がある。（早稲田大学）
（解） 相異なる ｎ＋１
個の整数を、 ａ1、ａ2、・・・、ａｎ、ａｎ+1 とし、これらを ｎ
で割った
余りを、それぞれ
ｒ1、ｒ2、・・・、ｒｎ、ｒｎ+1 とおく。（これが、鳩） ところで、整数を
ｎ
で割った余りは、０、１、２、・・・、ｎ−１ のいずれか。（これが、鳩ノ巣）
よって、鳩ノ巣原理により、
ｒ1、ｒ2、・・・、ｒｎ、ｒｎ+1 のうちに少なくとも２つ相等しい
ものがある。そのうちの２つについて差をとれば、その差は、ｎ の倍数になる。（終）
例題７ １００以下の自然数から、５１個の数を適当に選ぶと、互いに素となる ２つの数が
必ず存在する。
（解） 隣り合う数同士を組み合わせて、次のような ５０個の対を作る。
１＆２、３＆４、５＆６、・・・、９９＆１００ （これが、鳩ノ巣）
この「５０個の対」に対して、５１個の数を選んだ（これが、鳩）ので、鳩ノ巣原理によ
り、２つの数とも選ばれている対 Ａ＆Ｂ が存在する。このとき、隣り合う数同士は、
互いに素なので、題意を満たす。（終）
例題８ １９以下の自然数から、７個の数を適当に選ぶ。この７個の数の中から、いくつか
の相異なる数の組を ２ 組選んで、その和を等しくすることができる。
（解） ７個の数の中から、いくつかの相異なる数を選んで組を作るとき、その作り方は、
２7−１ ＝ １２７通りある。（これが、鳩）
また、そのような組の中で、
和が最大となるものは、１９＋１８＋１７＋１６＋１５＋１４＋１３＝１１２
和が最小となるものは、１
である。
したがって、和のとり得る値は、１、２、３、・・・・、１１２ （これが、鳩ノ巣）
よって、鳩ノ巣原理により、和が等しくなる組が少なくとも２つ存在する。
２つの組にもし、同じ数があれば、それらを取り除いても、和は等しいままで、しか
も、２つの組の数は、すべて異なるようにできる。（終）
（参考文献：ローレン・Ｃ・ラーソン 著 秋山 仁・飯田博和 訳
数学発想ゼミナール ＜１＞ （シュプリンガー・フェアラーク東京））
ＦＮさんが、この問題を考察された。（平成２３年１月２２日付け）
上記の問題で、「１９」を「２１」に変えても全く同じ形で証明できます。「１９」を「２３」に変え
る場合は、少し証明を変えればできます。
例題８’ ２３以下の自然数から７個の数を任意に選ぶ。この７個の数からいくつかの相異
なる数の組を２組選んでその和を等しくすることができる。
ＦＮさんが、例題８’の解答を与えられました。（平成２３年１月２５日付け）
（解） ７個の数の中から、いくつかの相異なる数を選んで組を作るとき、その作り方は、
２7−１＝１２７通りある。（これが、鳩）ここまでは例題と同じ。
（最大と最小について、例題８の（解）より少しだけ正確にする。）
７個の数のうち最小なものを
ａ
とする。そのような組の中で、和が最大となるものは、
２３＋２２＋２１＋２０＋１９＋１８＋ａ＝１２３＋ａ
で、和が最小となるものは、ａ である。
したがって、和のとり得る値は、 ａ 、ａ＋１ 、ａ＋２ 、・・・ 、ａ＋１２３ の１２４通りあ
る。（これが、鳩ノ巣） 以下は例題８の（解）と同じ。 （終）
例題８’では、例題８の「１９」を「２３」に変えましたが、まだまだ甘い結果で、もっと大きな数
で成り立ちそうです。ただ鳩の巣原理で証明できるのは、このあたりが限度かなと思います。
「４３」で成り立つらしいですが、簡単には証明できないと思われます。はっきり書いてはない
のですが、「４４」では反例があるのかなと思います。例題８の証明を参考に多少表現を変え
ます。（平成２３年１月２２日付け）
例題８” ４４以下の自然数７個をうまく選んで次の条件をみたすようにせよ。
７個の中から何個かを取りだして作った和はすべて異なる。
７個はかなり多いので、もう少し小さい数の場合から考えた方がよさそうです。そのために
問題を一般化した形で書きます。
例題８＾ ｋ以下の自然数ｎ個をうまく選んで次の条件をみたすようにせよ。
ｎ個の中から何個かを取りだして作った和はすべて異なる。
自然数 ｎ が与えられたとき、これが可能であるような最小の ｋ を求めよ。
条件をみたすようなn個の集合をＡと書くことにします。
ｎ＝１ のとき、 ｋ＝１ で、 Ａ＝｛１｝
ｎ＝２ のとき、 ｋ＝２ で、 Ａ＝｛１，２｝
ｎ＝３ のとき、 ｋ＝４ で、 Ａ＝｛１，２，４｝ ・・・・・ここまでは問題ないでしょう。
ｎ＝４ のとき、 Ａ＝｛１，２，４，８｝ が条件を満たすのは確かですが、Ａ＝｛３，５，６，７｝も
条件を満たすので、多分．．．ｋ＝７ → （確定）
ｎ＝５ のとき、 ｋ＝１３ で、 Ａ＝｛６，９，１１，１２，１３｝は条件を満たす。最小性は不明。
ｎ＝６、７ ぐらいで最小であるかどうかは別にして、条件を満たすＡを作って下さい。
Ａ＝｛１，２，４，８，１６，・・・｝が条件を満たすのは明らかなので、ｎ＝６、７の場合で、３２、
６４以下ですが、ｎ＝７の場合で、４４まで下がるとすれば、ｎ＝６の場合でも、３２よりかなり
小さい数かなと思います。
ＦＮさんからの続報です。（平成２３年１月２３日付け）
例題８’について、「２３」を「２５」に変えても鳩の巣原理を使ったきれいな証明がありました。
「２６」でもできますが、少し汚くなるので、「２５」にしておきます。
例題８’Ａ ２５以下の自然数から７個の数を任意に選ぶ。この７個の数からいくつかの相異
なる数の組を２組選んでその和を等しくすることができる。
ＦＮさんからの続報です。（平成２３年１月２５日付け）
例題８’Ａをやや強めた結果を証明する。少しだけだが強い結果である。
この７個の数から４個以下の相異なる数の組を２組選んでその和を等しくすることができる。
強い結果のほうが証明しやすいのは不思議であるが、もともと相当弱い結果なので、少々
強めても楽に成り立ち鳩ノ巣原理ではこちらの方が示しやすいようである。
（証明） ７個の数の中から、４個以下の相異なる数を選んで組を作るとき、その作り方は、
7Ｃ1＋7Ｃ2＋7Ｃ3＋7Ｃ4＝７＋２１＋３５＋３５＝９８通りある。(これが鳩)
この中で、和が最大となるのは、 ２５＋２４＋２３＋２２＝９４
最小となるのは、 １
従って、和の取りうる値は、 １、２、・・・、９４ で、９４通り。(これが鳩の巣)
以下は例題８の（解）と同じ。 （証終）
２５を２６に変えると、最大が ２６＋２５＋２４＋２３＝９８ となり、鳩と鳩の巣が同数とな
る。だから、ただちに結論を出せないが、１から９８まですべての値をとることになり、和が
９８になるものがあることから、２６、２５、２４、２３ を含まなければならない。
そうすると、 ２６＋２３＝２５＋２４。
２６まで証明できたが、４３で成り立つらしいから、まだまだ弱い結果である。もう少し細か
い議論をすれば、２７や２８とかはできるかもしれないが、４３までいけるとは思えない。別の
考え方が必要でしょう。
攻略法さんが、例題８＾について調べられた。（平成２３年１月２３日付け）
ｎ＝１ のとき、 Ａ＝｛１｝ よって、 ｋ＝１
ｎ＝２ のとき、 Ａ＝｛１，２｝ よって、 ｋ＝２
ｎ＝３ のとき、 Ａ＝｛１，２，４｝ または Ａ＝｛２，３，４｝ よって、 ｋ＝４
ｎ＝４ のとき、 Ａ＝｛１，２，４，８｝ または Ａ＝｛３，５，６，７｝ よって、 ｋ＝７
ｎ＝５ のとき、 Ａ＝｛３，６，１１，１２，１３｝ または Ａ＝｛６，９，１１，１２，１３｝
または Ａ＝｛１，２，４，８，１６｝ よって、 ｋ＝１３
ｎ＝６ のとき、 Ａ＝｛１，２，４，８，１６，３２｝ または Ａ＝｛１１，１７，２０，２２，２３，２４｝
よって、 ｋ＝２４
ｎ＝７ のとき、
Ａ＝｛１，２，４，８，１６，３２，６４｝ 、・・・、Ａ＝｛２０，３１，３７，４０，４２，４３，４４｝
よって、 ｋ＝４４
ＦＮさんからのコメントです。（平成２３年１月２３日付け）
１、２、４、７、１３、２４、４４、・・・ を、オンライン整数列大辞典で検索しました。
Ｆｉｂｏｎａｃｃｉ数列の親戚のＴｒｉｂｏｎａｃｃｉ数列というそうです。ｎ＝１からｎ＝７まであってい
ます。これは偶然でしょうか、それとも必然でしょうか。
※Ｔｒｉｂｏｎａｃｃｉ 数列
０，０，１，１，２，４，７，１３，２４，４４，８１，１４９，２７４，・・・・
のように、前の３項の和として新しい項が定義される数列である。
すなわち、数列｛ａｎ｝がＴｒｉｂｏｎａｃｃｉ数列とは、漸化式
ａ0＝０、ａ1＝０、ａ2＝１、 ａｎ+3＝ａｎ＋ａｎ+1＋ａｎ+2 （ｎ＝０，１，２，３，・・・）
で定義される数列を言う。
ＦＮさんからの続報です。（平成２３年１月２４日付け）
攻略法さんの ｎ≦7 の範囲での結果によると、ｋ が Ｔｒｉｂｏｎａｃｃｉ数列(ただし、初期値を
ｔ1＝１、ｔ2＝２、ｔ3＝４ としたもの)になっていますが、それだけではなくて、それを実現する
Ａも Ｔｒｉｂｏｎａｃｃｉ 数列から得られるものになっています。
例えば、ｎ＝７ のときの 20， 31， 37， 40， 42， 43， 44
において、最後の数から他の
数を引くと、 1， 2， 4， 7， 13， 24 となり、 ｔｒｉｂｏｎａｃｃｉ
数列です。
すべて、この形になっています。ただし、２つあるときはその一方がそうです。
即ち、 ｔｎ，
ｔｎ−ｔ1， ｔｎ−ｔ2，・・・，
ｔｎ−ｔｎ-1 の形です。
こうなると、偶然であるよりは必然である方がありそうなものですが、これが条件を満たす
ことはとても言えそうな気はしません。さらに条件を満たす中で最小であることも言う必要が
あります。
Ａを、 ａ1，
ａ2， ･･･， ａn とすると、条件は、ｃｔ
が ０、１、−１ のいずれかとして、
Σｃｔ・ａｔ＝０ が、すべての ｃｔ
が０のとき以外成り立たない
ことになります。あるいは、両辺に、Σａｔ を加えて、ｃｔ＋１ を改めて
ｃｔ
とおいて、
Σｃｔ・ａｔ＝Σａｔ (ただし、ｃｔ＝０、１、２) がすべての
ｃｔ が １ のとき以外成り立たない
と言ってもいいです。
３つの項の和が次の項になるという Ｔｒｉｂｏｎａｃｃｉ の性質が、なぜこの問題に絡む可能性
があるのか全くわかりません。
例題８＾ ｋ以下の自然数ｎ個をうまく選んで次の条件をみたすようにせよ。
ｎ個の中から何個かを取りだして作った和はすべて異なる。
自然数 ｎ が与えられたとき、これが可能であるような最小の ｋ を求めよ。
について、攻略法さんが考察された。（平成２３年１月２５日付け）
２進法で、連続する自然数を重複することなく表現できるので、Ａ＝｛１，２，４，８，・・・｝は
題意を満たす。
Ｆｉｂｏｎａｃｃｉ数列やＴｒｉｂｏｎａｃｃｉ数列のような前 ｐ 項の和で生成される数列を使って、その
右端Ａ（ｎ）を小さくできる。
ｎ＝７までは確認して、ｎ＝８を検証中。９以上は未確認．．．。
前２項の和( 1 2 … ) 第２項までは２のべき乗のＦｉｂｏｎａｃｃｉ数列
| ｎ＝２ |
|
ｎ＝３ |
|
ｎ＝４ |
1 2
└ 1 ┘差 |
|
2 3 4
└ 1 ┘差
└ 2 ─┘ |
|
2 3 4 5
└ 1 ┘差
└ 2 ─┘
└ 3 ──┘ |
２＋３＝５、２＋５＝３＋４ で題意を満たさない。
したがって、表現できるのは、ｎ＝３までとなる。
前３項の和( 1 2 4 7 13 24 44 …) 第３項までは２のべき乗のＴｒｉｂｏｎａｃｃｉ数列
| ｎ＝４ |
|
ｎ＝５ |
3 5 6 7
└ 1 ┘差
└ 2 ─┘
└ 4 ──┘ |
|
6 9 11 12 13
└ 1 ┘差
└ 2 ─┘
└ 4 ───┘
└ 7 ─────┘ |
ｎ＝６ → 11 17 20 22 23 24
ｎ＝７ → 20 31 37 40 42 43 44
ｎ＝８ → 40 60 71 77 80 82 83 84
ＦＮさんからのコメントです。（平成２３年１月２５日付け）
上記の計算から、ｎ＝７まではＴｒｉｂｏｎａｃｃｉでいけたけど、ｎ＝８になると無理ということで
すね。Ｔｅｔｒａｎａｃｃｉとかが役に立ったりするのかもしれません。Ｔｒｉｂｏｎａｃｃｉでいければ面白
いけどなと思いましたが、やはりそんなに甘い話はなさそうですね。
攻略法さんの考察の続きです。
前４項の和(1 2 4 7 14 27 52 100 … ) 同様
ｎ＝５ → 6 9 11 12 13
ｎ＝６ → 11 18 21 23 24 25
ｎ＝７ → 21 34 41 44 46 47 48
ｎ＝８ → 44 69 82 89 92 94 95 96
ｎ＝９ → 89 137 162 175 182 185 187 188 189
前４項の和( 1 2 4 8 15 29 56 108 208 … ) 同様
ｎ＝５ → 6 10 12 13 14
ｎ＝６ → 12 19 23 25 26 27
ｎ＝７ → 23 37 44 48 50 51 52
ｎ＝８ → 44 71 85 92 96 98 99 100
ｎ＝９ → 92 144 171 185 192 196 198 199 200
ｎ＝１０ → 185 285 337 364 378 385 389 391 392 393
前５項の和( 1 2 4 8 16 31 61 120 236 464 … ) 同様
ｎ＝１１ → 356 584 700 759 789 804 812 816 818 819 820
攻略法さんの考察の続きです。（平成２３年１月２７日付け）
一日越しの結果になりました。
ｎ＝８ → 40 60 71 77 80 82 83 84
39 59 70 77 78 79 81 84
20 40 71 77 80 82 83 84
ｎ＝７ のとき、「20 31 37 40 42 43 44」で、
ｎ＝８ のとき、「40 60 71 77 80 82 83 84」ですから、場合の数による方
法だと、上限が４４、８４から大雑把で４４7、８４8回の検証になります。ｎ＝７ でもかなり厳し
いものになります。
隣接 ｐ 項の和の数列を使って、A(ｎ)＝２ｎ-1 を小さくする方法で当たりをつけるのがよい
と思います。ｎ≦８ では、最小になっています。
ＦＮさんからのコメントです。（平成２３年１月２７日付け）
有難うございました。とても難しそうです。ｎ＝５ のとき、ｋ＝１３ ぐらいは証明できないか
と思ったのですが、なかなかできません。とりあえず、しばらく寝かせるしかなさそうです。
この問題について、らすかるさんからの情報です。（平成２３年１月２８日付け）
オンライン整数列大辞典のこちらに、Conway-Guy sequenceと言われる漸化式
があるようで、証明もされているようです。具体例は、こちらにあるそうです。
らすかるさんによれば、続きは、次のような感じになるとのことです。
ｎ＝１６ のとき
{8498,12821,15021,16141,16711,16996,17144,17221,17261,17281,17292,17298,
17301,17303,17304,17305}
ｎ＝１７ のとき
{16996,25494,29817,32017,33137,33707,33992,34140,34217,34257,34277,34288,
34294,34297,34299,34300,34301}
ｎ＝１８ のとき
{33707,50703,59201,63524,65724,66844,67414,67699,67847,67924,67964,67984,
67995,68001,68004,68006,68007,68008}
ｎ＝１９ のとき
{66844,100551,117547,126045,130368,132568,133688,134258,134543,134691,
134768,134808,134828,134839,134845,134848,134850,134851,134852}
ｎ＝２０ のとき
{132568,199412,233119,250115,258613,262936,265136,266256,266826,267111,
267259,267336,267376,267396,267407,267413,267416,267418,267419,267420}
ＦＮさんからのコメントです。（平成２３年１月２８日付け）
やはり解けていましたか。きれいな問題設定だから、解けていて不思議はないですね。一
般の場合の解答は多分理解できないでしょうが、せめてｎ＝５ぐらいだけでも証明を理解で
きないか、検索して調べてみます。有難うございました。
（追記） 平成２３年２月１日付け
例題８に関連して、鳩ノ巣原理とは関係ないが、次のような入試問題に興味を持った。
慶應義塾大学 理工学部（１９９１） （穴埋め式なので、記述式に改題）
１から２ｎまでの２ｎ個の整数がある。ただし、ｎは３以上の整数とする。次の２つの
性質（Ａ）、（Ｂ）をもつ４つの整数 ａ、ｂ、ｃ、ｄ をこの２ｎ個の整数から選ぶ選び方は
何通りあるかを求めたい。次の問いに答えよ。
（Ａ） １≦ａ＜ｂ＜ｃ＜ｄ≦２ｎ （Ｂ） ａ＋ｄ＝ｂ＋ｃ
（１） このような選び方が可能であるような ａ、ｂ の値を固定したとき、２つの整数
ｃ、ｄ の選び方は何通りあるか。
（２） ａ の値だけを固定したとき、３つの整数 ｂ、ｃ、ｄ の選び方は何通りあるか。
（３） （１）（２）を用いて、求める選び方は何通りあるか。
（答え） （１） ２ｎ−２ｂ−ａ （通り）
（２） ａ＝２ｋ−１ （ｋは整数で、１≦ｋ≦ｎ−１） のとき、 （ｎ−ｋ）2 （通り）
ａ＝２ｋ （ｋは整数で、１≦ｋ≦ｎ−２） のとき、（ｎ−ｋ−１）（ｎ−ｋ） （通り）
（３） ｎ（ｎ−１）（４ｎ−５）/６ （通り）
（解）（１） ａ、ｂ
を固定するとき、 ０≦ａ＜ｂ＜ｃ＜ｄ≦２ｎ 、 ｄ＝ｂ＋ｃ−ａ
ｃ＝ｂ＋１ のとき、 ｄ＝２ｂ−ａ＋１
ｃ＝ｂ＋２ のとき、 ｄ＝２ｂ−ａ＋２
・・・・・・・・・・・・・・・・・・
ｄ＝２ｎ となるまで続く。
よって、ｃ、ｄ
の取り得る場合の数は、２ｎ−（２ｂ−ａ＋１）＋１＝２ｎ−２ｂ＋ａ （通り）
（２） （１）より、 ２ｂ−ａ＋１≦２ｎ なので、 ２ｂ≦ａ＋２ｎ−１
ａ＝２ｋ（ｋは整数で、ｋ≧１）のとき、 ２ｂ≦ａ＋２ｎ−１＝２ｋ＋２ｎ−１
ｂ≧２ｋ＋１ なので、 ２ｋ＋１≦ｂ≦ｋ＋ｎ−１ より、ｂの取り得る値は、
（ｋ＋ｎ−１）−（２ｋ＋１）＋１＝ｎ−ｋ−１ （通り）
よって、ｂ、ｃ、ｄ
の取り得る場合の数は、
（２ｎ＋２ｋ）（ｎ−ｋ−１）−２｛（２ｋ＋１）＋（ｋ＋ｎ−１）｝（ｎ−ｋ−１）/２
＝（ｎ−ｋ−１）（２ｎ＋２ｋ−３ｋ−ｎ）
＝（ｎ−ｋ−１）（ｎ−ｋ） （通り）
ａ＝２ｋ−１（ｋは整数で、ｋ≧１）のとき、 ２ｂ≦ａ＋２ｎ−１＝２ｋ＋２ｎ−２
ｂ≧２ｋ なので、 ２ｋ≦ｂ≦ｋ＋ｎ−１ より、ｂの取り得る値は、
（ｋ＋ｎ−１）−２ｋ＋１＝ｎ−ｋ （通り）
よって、ｂ、ｃ、ｄ
の取り得る場合の数は、
（２ｎ＋２ｋ−１）（ｎ−ｋ）−２｛２ｋ＋（ｋ＋ｎ−１）｝（ｎ−ｋ）/２
＝（ｎ−ｋ）（２ｎ＋２ｋ−３ｋ−ｎ）
＝（ｎ−ｋ）2 （通り）
（３） ａ＝２ｋ（ｋは整数で、ｋ≧１）のとき、 ２ｋ＋１≦ｂ≦ｋ＋ｎ−１ なので、
ｋ＝１、２、・・・、ｎ−１
このときの取り得る場合の数は、
Σ（ｎ−ｋ−１）（ｎ−ｋ）
＝ｎ（ｎ−１）・（ｎ−１）−（２ｎ−１）・ｎ（ｎ−１）/２＋ｎ（ｎ−１）（２ｎ−１）/６
＝ｎ（ｎ−１）（６ｎ−６−６ｎ＋３＋２ｎ−１）/６
＝ｎ（ｎ−１）（ｎ−２）/３
ａ＝２ｋ−１（ｋは整数で、ｋ≧１）のとき、 ２ｋ≦ｂ≦ｋ＋ｎ−１ なので、
ｋ＝１、２、・・・、ｎ−１
このときの取り得る場合の数は、
Σ（ｎ−ｋ）2
＝ｎ2・（ｎ−１）−２ｎ・ｎ（ｎ−１）/２＋ｎ（ｎ−１）（２ｎ−１）/６
＝ｎ（ｎ−１）（６ｎ−６ｎ＋２ｎ−１）/６
＝ｎ（ｎ−１）（２ｎ−１）/６
よって、求める場合の数は、
ｎ（ｎ−１）（ｎ−２）/３＋ｎ（ｎ−１）（２ｎ−１）/６
＝ｎ（ｎ−１）（４ｎ−５）/６ （終）
例題９ どんな自然数 N に対しても、フィボナッチ数列は、 ０ 以外の mod N 周期 ｐ を
持つ。
（解） 解答は、こちらを参照のこと。
例題１０ 平面上の点（ ｘ ， ｙ ）で、ｘ ， ｙ がともに整数であるとき、格子点といわれる。
いま、平面上の相異なる５個の格子点から２個の格子点を選んでできる線分の
中点を考える。このときできる中点のうち少なくとも一つは格子点になるものが
ある。
（解） 格子点のタイプは、
（偶数，偶数）、（偶数，奇数）、（奇数，偶数）、（奇数，奇数）
の４通りある。（これが、鳩ノ巣）
いま、格子点が５個ある（これが、鳩）ので、鳩ノ巣原理により、少なくとも２つ同じ
タイプの格子点が存在する。それらを結ぶ線分の中点が格子点となる。（終）
例題１１ １ から １００ までの１００個の整数がある。この中から、 ５５個の整数をどのよ
うに選んでも必ず、その ５５ 個の中に、２つの相異なる数で、差が、９ となるもの
が存在する。
（解） 任意に選んだ５５個の整数を、 １≦ａ1＜ａ2＜・・・＜ａ54＜ａ55≦１００ とする。
これらの全てに９を加えて、１０≦ａ1＋９＜ａ2＋９＜・・・＜ａ54＋９＜ａ55＋９≦１０９
このとき、 ａ1、ａ1＋９、・・・、ａ55、ａ55＋９ と１１０個の整数がある（これが、鳩）。
ところが、これらは、１ から １０９ までの１０９個の整数である（これが、鳩ノ巣）。
したがって、鳩ノ巣原理により、ａｍ＝ａｎ＋９ となる２数 ａｍ、ａｎ が存在する。
この２数の差が９となる。（終）
ＦＮさんが、この問題を一般化された。（平成２３年１月１５日付け）
例題１１’ １から ｎ までの ｎ 個の整数がある。この中から ｋ 個の整数をどのように選ん
でも必ず、その ｋ 個の中に、２つの相異なる数で、差が、ｍ となるものが存在す
る。自然数 ｎ、ｍ が与えられたとき、この命題が成り立つような自然数 ｋ の最小
値を求めよ。
（解） 任意に選んだ ｋ 個の整数を、 １≦ａ1＜ａ2＜・・・＜ａｋ≦ｎ とする。
これらの全てに ｍ を加えて、ｍ＋１≦ａ1＋ｍ＜ａ2＋ｍ＜・・・＜ａｋ＋ｍ≦ｎ＋ｍ
このとき、 ａ1、ａ1＋ｍ、・・・、ａｋ、ａｋ＋ｍ と ２ｋ 個の整数がある（これが、鳩）。
条件を満たすために、これらは、１ から ｎ＋ｍ までの ｎ＋ｍ個の整数（これが、鳩
ノ巣）で、 ｎ＋ｍ＋１＝２ｋ
したがって、求める最小値は、 ｋ＝（ｎ＋ｍ＋１）/２ （終）
FNさんからのコメントです。（平成２３年１月１７日付け）
出題したときに、「大体できているのもありますが」と書いたのはこれのつもりで、考えてた
答えは、[(ｎ＋ｍ＋１)/２]です。ただ、このときに成り立つのは間違いないですが、それより
小さいときに成り立たないことを示そうとしてできないことに気づきました。
ｎ＝１００、ｍ＝９ のときは、たまたまこれが最小値であったのですが、一般には最小値
ではありません。
例えば、ｎ＝１００
を、１０１から１０８までの数に変えて、ｍは９のままのとき、ｋは５５のま
まです。まず、例題１１の ｎ＝１００ を ｎ＝１０５
とかに変えたものを証明して、それから一
般化を考えた方がいいと思います。
ＨＮ「ケンスー」さんが、この問題の解答を寄せられた。（平成２３年１月１７日付け）
ｎ＝ａｍ＋ｂ （ａ∈N、０≦ｂ≦ｍ−１） と表されるとき、ｋ
の最小値は、
([ａ/２]＋１)ｂ＋[(ａ＋１)/２](ｍ−ｂ)＋１
と表される。ただし、［ｘ］はガウス記号で、ｘ
を超えない最大の整数を表す。
例 ｎ＝１００、ｍ＝９ のとき、 ａ＝１１ 、 ｂ＝１
このとき、 ([ａ/２]＋１)ｂ＋[(ａ＋１)/２](ｍ−ｂ)＋１＝(５＋１)・１＋６・（９−１)＋１
＝６＋４８＋１＝５５
よって、 ｋ＝５５ である。
例 ｎ＝１０５、ｍ＝９ のとき、 ａ＝１１ 、 ｂ＝６
このとき、 ([ａ/２]＋１)ｂ＋[(ａ＋１)/２](ｍ−ｂ)＋１＝(５＋１)・６＋６・（９−６)＋１
＝３６＋１８＋１＝５５
よって、 ｋ＝５５ である。
（コメント） ｎ＝１００ から多少増えても、ｋ＝５５のままなんですね！不思議です。
攻略法さんが、私のコメントに対し、反例となる豆をまいて鳩を集められました。
（平成２３年１月２０日付け）
ｎ が大きいと、nＣｋ が天文学的数値になるということで、小さい値での調査とのことです。
＜結果＞ 反例となる ｋ 個の数（その１つ）
+1 +2 +3 +4 … +(m-1) +m
0m： 1 2 3 4 … m-1 m
2m： 2m+1 2m+2 2m+3 2m+4 … 2m+(m-1) 2m+m
4m： 4m+1 4m+2 4m+3 4m+4 … 4m+(m-1) 4m+m
6m： 6m+1 6m+2 6m+3 6m+4 … 6m+(m-1) 6m+m
：
：
最後は
(2p)m: (2p)m+1 (2p)m+2 … n pは０以上の整数
または
(2p)m: (2p)m+1 (2p)m+2 (2p)m+3 (2p)m+4 … (2p)m+(m-1) (2p)m+m
(2p+1)m: (2p+1)m+1 (2p+1)m+2 … n
Ｅｘｃｅｌ ＶＢＡ サンプル
Sub Test11()
Let N = 20 '自然数n
Let M = 3 '1≦m＜n
Debug.Print "n="; N; "m="; M
Let Q = Int(N / M) 'nをmで割ったときの商をq、余りをrとする。n=q*m+r(p∈N,0≦r＜m)
Let R = N - Q * M
Debug.Print "k="; (Int(Q / 2) + 1) * R + Int((Q + 1) / 2) * (M - R) + 1
Dim A(50)
For k = 2 To N '２≦k≦n
Debug.Print "k="; k
For i = 1 To k 'k個の数A1,A2,…,Ak（nCk通り）を列挙する
Let A(i) = i
Next i
Do
For i = 1 To k - 1 'AiとAjが題意を満たすか
For j = i + 1 To k
If A(j) - A(i) = M Then Exit For 'Aj-Ai=m（Ai＜Aj）なら
Next j
If j <= k Then Exit For '１つでも見つかればよい
Next i
If i > k - 1 Then '見つからなければ、反例となる
For j = 1 To k 'k個の数を表示する
Debug.Print A(j);
Next j
Debug.Print
Exit Do '１つのみ!!! ※ここをコメントアウトするとすべて表示する
End If
Loop While NextComb(A, N, k) = 1 '次へ
Debug.Print
Next k
End Sub
Function NextComb(ByRef A(), ByVal N, ByVal R) '辞書式順序で次の組合せを返す
Let NextComb = 0 '完了
For i = R To 1 Step -1
If A(i) < N - R + i Then 'i〜N-R+iで更新する
Let A(i) = A(i) + 1
For j = i + 1 To R 'A(i)<A(i+1)< … <A(R) 最初の並び
Let A(j) = A(j - 1) + 1
Next j
Let NextComb = 1 '未了
Exit Function
End If
Next i
End Function
ケンスーさんの解答に対して、ＦＮさんからのコメントです。（平成２３年１月１７日付け）
ｎ、ｍ
に対して、ｋ
が確定すれば十分です。ただし、その数以上であれば成り立つことと、
その数未満であれば成り立たないことの証明をしてください。私が得た式と見かけは異なり
ますがどうやら同じ式のようです。
例題１１’について、ＦＮさんの考察です。（平成２３年１月２４日付け）
ｎ を２ｍで割った商がｑで余りがｒであるとき、
ｋ＝ｑｍ＋ｍｉｎ（ｍ，ｒ）＋１ である。
○ ｋ≧ｑｍ＋ｍｉｎ（ｍ，ｒ）＋１ のとき成り立つこと
ｎ＝２ｍｑ＋ｒ （０≦ｒ＜２ｍ）である。１からｎまでのｎ個の整数を、次のようにグループに
分ける。
１〜２ｍ、２ｍ＋１〜４ｍ、４ｍ＋１〜６ｍ、･･･、２ｍ（ｑ−１）＋１〜２ｍｑ、２ｍｑ＋１〜２ｍｑ＋ｒ
(ただし、ｒ＝０ のとき、最後のグループはない)
各グループは、連続した２ｍ個(ただし、最後のグループは、ｒ個)からなる。選ばれたｋ個の
整数がどのグループに属するかを考える。
どのグループもｍ個以下(最後のグループは、ｍｉｎ（ｍ，ｒ）以下)とすると、
ｋ≦ｑｍ＋ｍｉｎ（ｍ，ｒ）
となって仮定に反するから、どれかのグループに、ｍ＋１個入っている。
ｍで割った余りは、ｍ通りしかないから、このうちに余りの等しいものがある。
その差は、ｍの倍数であるが、２ｍ以上である可能性はないから、ｍである。
○ ｋ≦ｑｍ＋ｍｉｎ（ｍ，ｒ） のとき成り立たないこと
１〜ｍ、２ｍ＋１〜３ｍ、４ｍ＋１〜５ｍ、･･･、
２ｍ（ｑ−１）＋１〜２ｍ（ｑ−１）、２ｍｑ＋１〜２ｍｑ＋ｍｉｎ（ｍ，ｒ）
が条件を満たさないのは明らかであり、その部分集合も条件を満たさない。
○ ケンスーさんの結果と一致すること
ｎ＝２ｍｑ＋ｒ で、ｒ＜ｍ のときは、 ａ＝２ｑ 、ｂ＝ｒ で、
［ａ/２］＝ｑ 、 ［（ａ＋１）/２］＝ｑ
だから、 ([ａ/２]＋１)ｂ＋[(ａ＋１)/２](ｍ−ｂ)＋１＝（ｑ＋１）ｒ＋ｑ(ｍ−ｒ)＋１
＝ｍｑ＋ｒ＋１＝ｍｑ＋ｍｉｎ（ｍ，ｒ）＋１
ｒ≧ｍ のときは、ｎ＝２ｍｑ＋ｒ＝（２ｑ＋１）ｍ＋（ｍ−ｒ） で、ａ＝２ｑ＋１、ｂ＝ｍ−ｒ より、
［ａ/２］＝ｑ 、 ［（ａ＋１）/２］＝ｑ＋１
だから、 ([ａ/２]＋１)ｂ＋[(ａ＋１)/２](ｍ−ｂ)＋１＝（ｑ＋１）（ｍ−ｒ）＋（ｑ＋１）ｒ＋１
＝（ｑ＋１）ｍ＋１
＝ｍｑ＋ｍ＋１
＝ｍｑ＋ｍｉｎ（ｍ，ｒ）＋１
ＦＮさんが上記で述べられた新しい問題です。（平成２３年１月１８日付け）
例題１１Ａ １から１０５までの１０５個の整数がある。この中から５５個の整数をどのよう
に選んでもその５５個の中にその差が９となる２つの数が必ず存在する。
例題１１と同じ証明ではできません。もう少し細かい議論が必要です。
（解） １から１０５までの整数を、次の６つのグループに分ける。
１〜１８ 、１９〜３６ 、 ３７〜５４ 、 ５５〜７２ 、 ７３〜９０ 、 ９１〜１０５
選んだ５５個が上のグループに何個入るかを考える。
すべてのグループに９個以下しか入らないとすると、６×９＝５４個以下であるから少なく
とも１つのグループに１０個以上入ることになる。
連続した１８個(またはそれ以下)の数の中に、１０個の数が入っていることになる。
９で割った余りは９通りしかないので、９で割った余りが等しい２つの数がある。
その差は９の倍数であるが、18以上にはなりえないから９である。 （終）
後半は鳩ノ巣原理そのものですが、前半もその一種なので鳩ノ巣原理を２回使ったという
感じです。５５が最善であること、即ち、５４であれば成り立たないことは、
１〜９ 、１９〜２７ 、 ３７〜４５ 、 ５５〜６３ 、 ７３〜８１ 、 ９１〜９９
の５４個が反例になることからわかります。また、１０５を９９から１０８までの数に変えてもそ
のまま成り立ちます。この証明と同様にすれば、例題１１’もできます。
例題１２ １ から ４ までの自然数からいくつか選んで作った７個の集合 Ａ1、Ａ2、・・・、Ａ7
がすべて異なるとき、Ａｍ⊂Ａｎ となる Ａｍ 、 Ａｎ が存在する。
（解） 集合 ｛ １ ， ２ ， ３ ， ４ ｝ の部分集合は全部で、２4＝１６個ある。
それらを列挙すると、、
φ、｛ １ ｝、｛ ２ ｝、｛ ３ ｝、｛ ４ ｝、｛ １ ， ２ ｝、｛
１ ， ３ ｝、｛ １ ， ４ ｝、｛ ２ ， ３ ｝、
｛ ２ ， ４ ｝、｛ ３ ， ４ ｝、｛ １ ， ２ ， ３ ｝、｛ １
， ２ ， ４ ｝、｛ １ ， ３ ， ４ ｝、
｛ ２ ， ３ ， ４ ｝、｛ １ ， ２ ， ３ ， ４ ｝
これらを、どの２つも包含関係を持つように分類すると、
Ｂ1 ： φ⊂｛ １ ｝⊂｛ １ ， ２ ｝⊂｛ １ ， ２ ， ３ ｝
Ｂ2 ： ｛ ２ ｝⊂｛ ２ ， ３ ｝
Ｂ3 ： ｛ ３ ｝⊂｛ １ ， ３ ｝⊂｛ １ ， ３ ， ４ ｝
Ｂ4 ： ｛ ２ ， ４ ｝⊂｛ ２ ， ３ ， ４ ｝
Ｂ5 ： ｛ ４ ｝⊂｛ １ ， ４ ｝⊂｛ １ ， ２ ， ４ ｝
Ｂ6 ： ｛ ３ ， ４ ｝⊂｛ １ ， ２ ， ３ ， ４ ｝
の６個（これが、鳩ノ巣）に分けられる。（分類の組合せは他にもある！）
これに対して、７個の集合 Ａ1、Ａ2、・・・、Ａ7 がある（これが、鳩）ので、ある Ｂｋ に
少なくとも２つ Ａｍ 、 Ａｎ が含まれ、Ａｍ⊂Ａｎ が成り立つ。（終）
ＦＮさんが、この問題を一般化された。（平成２３年１月１５日付け）
例題１２’ １から ｎ までの自然数からいくつか選んで作った ｋ 個の集合 Ａ1、Ａ2、・・・、Ａｋ
がすべて異なるとき、Ａｍ⊂Ａｎ となる Ａｍ 、 Ａｎ が存在する。
自然数 ｎ が与えられたとき、この命題が成り立つような自然数
ｋ の最小値を
求めよ。
これについて、一般の ｎ だと雲を掴むような話のような．．．雰囲気なので、ｎ＝５
として
実験してみた。
集合 ｛ １ ， ２ ， ３ ， ４， ５ ｝ の部分集合は全部で、２5＝３２個ある。
それらを列挙すると、、
φ、｛ １ ｝、｛ ２ ｝、｛ ３ ｝、｛ ４ ｝、｛ ５ ｝、｛ １ ， ２ ｝、｛
１ ， ３ ｝、｛ １ ， ４ ｝、｛ １ ， ５ ｝、
｛ ２ ， ３ ｝、｛ ２ ， ４ ｝、｛ ２ ， ５ ｝、｛ ３ ， ４ ｝、｛ ３
， ５ ｝、｛ ４ ， ５ ｝、｛ １ ， ２ ， ３ ｝、
｛ １ ， ２ ， ４ ｝、｛ １ ， ２ ， ５ ｝、｛ １ ， ３ ， ４ ｝、｛
１ ， ３ ， ５ ｝、｛ １ ， ４ ， ５ ｝、
｛ ２ ， ３ ， ４ ｝、｛ ２ ， ３ ， ５ ｝、｛ ２ ， ４ ， ５ ｝、｛
３ ， ４ ， ５ ｝、｛ １ ， ２ ， ３ ， ４ ｝、
｛ １ ， ２ ， ３ ， ５ ｝、｛ １ ， ２ ， ４ ， ５ ｝、｛ １ ， ３ ，
４ ， ５ ｝、｛ ２ ， ３ ， ４ ， ５ ｝、
｛ １ ， ２ ， ３ ， ４， ５ ｝
これらを、どの２つも包含関係を持つように分類すると、
Ｂ1 ： φ⊂｛ １ ｝⊂｛ １ ， ２ ｝⊂｛ １ ， ２ ， ３ ｝⊂｛ １ ， ２ ，
３ ， ４ ｝
Ｂ2 ： ｛ ２ ｝⊂｛ ２ ， ３ ｝⊂｛ ２ ， ３ ， ４ ｝⊂｛ ２ ， ３ ， ４
， ５ ｝
Ｂ3 ： ｛ ３ ｝⊂｛ ３ ， ４ ｝⊂｛ ３ ， ４ ， ５ ｝
Ｂ4 ： ｛ ４ ｝⊂｛ ４ ， ５ ｝⊂｛ ２ ， ４ ， ５ ｝
Ｂ5 ： ｛ ５ ｝⊂｛ ２ ， ５ ｝⊂｛ １ ， ２ ， ５ ｝
Ｂ6 ： ｛ １ ， ３ ｝⊂｛ １ ， ３ ， ４ ｝⊂｛ １ ， ３ ， ４ ， ５ ｝
Ｂ7 ： ｛ １ ， ４ ｝⊂｛ １ ， ４ ， ５ ｝
Ｂ8 ： ｛ １ ， ５ ｝⊂｛ １ ， ３ ， ５ ｝⊂｛ １ ， ２ ， ３ ， ５ ｝⊂｛
１ ， ２ ， ３ ， ４， ５ ｝
Ｂ9 ： ｛ ２ ， ４ ｝⊂｛ １ ， ２ ， ４ ｝⊂｛ １ ， ２ ， ４ ， ５ ｝
Ｂ10 ： ｛ ３ ， ５ ｝⊂｛ ２ ， ３ ， ５ ｝
の１０個（これが、鳩ノ巣）に分けられる。（分類の組合せは他にもある！）
したがって、鳩ノ巣原理を用いて、ある Ｂｋ に少なくとも２つ Ａｍ 、 Ａｎ が含まれ、Ａｍ⊂Ａｎ
が成り立つようにするためには、最低１１個の集合 Ａ1、Ａ2、・・・、Ａ11 （これが、鳩）があれ
ばよい。
よって、 ｎ＝５ のとき、 ｋ＝１１ である。
ｎ＝４ のとき、 ｋ＝７ であるわけだが、これらに規則性はあるのだろうか？
FNさんからのコメントです。（平成２３年１月１７日付け）
「ｎ＝４のときの鳩の巣は６個、ｎ＝５のときの鳩の巣は１０個」において、
「６」は、4Ｃ2＝６ で、「１０」は、5Ｃ2＝5Ｃ3＝１０
です。一般に、ｎ に対して、nＣr のうち最大のもの、即ち、
ｒ＝[ｎ/２] のときの
nＣr が鳩の巣の個数になると予想されます。
要素の個数が ｒ 個である部分集合同士の間に包含関係はないので、鳩の巣の個数は
nＣr 以上です。あとは、実際に、 nＣr 個の鳩の巣があることを示せば十分です。これをど
うやって証明するかですが、２部グラフに関するホールの結婚定理というのを使えばできそ
うです。もっと簡単にできるかどうかわかりません。
この問題について、ＨＮ「ａｔ」さんが、解答を寄せられた。（平成２３年１月１７日付け）
シュペルナー族の最大サイズは、 ｎＣ[ｎ/2]
です。したがって、
互いに異なる k 個の部分集合
A1、A2、･･･、Ak
をどのように選び出しても必ず
Aｓ⊂Aｔ となる
Aｓ、Aｔ が存在するような ｋ の最小値は、
ｎＣ[ｎ/2]＋１
ですね。
ＦＮさんからのコメントです。（平成２３年１月１７日付け）
グラフ理論を持ちださないで証明できるのは十分ありうることだと思っていました。ただ、私
は、Sperner's
theorem はもちろん、その証明で使われている LYM inequality
も知りません。
ホールの結婚定理は知っていますが、ホールの結婚定理を使った証明と LYM
inequality
を使った証明とどちらがわかりやすいかはわかりません。
さらに、ＦＮさんからの続報です。（平成２３年１月１８日付け）
Sperner's theorem というのは、まさに、(2)に対する答えそのものでした。鳩ノ巣原理を使
った証明にはなりませんが、ホールの結婚定理を使って鳩ノ巣原理に持ち込むより簡単な
証明になるようです。
Sperner's
theorem ｎ 個の要素を持つ集合Uの部分集合の族
A1、A2、･･･、Ak
がどの２つを取っても包含関係がないとき、 ｋ≦nＣm である。
ただし、ｍ＝[ｎ/２] とする。
例題１２’は、「ある２つについて包含関係がある」と言っているので、 ｋ≧nＣm＋１ となり
ます。
証明は、最大鎖(maximal
chain)の数を、２通りで数えるというものです。
鎖(chain)とは、Uの部分集合の列
B1⊂B2⊂B3⊂･･･⊂Br
をいう。ただし、⊂は真部分集
合の意味で使う。最大鎖とは、これ以上延ばせない鎖をいう。
最大鎖は、B0=φ
で、B1は１個の要素を持ち、B2は２個の要素を持ち、･･･、Bn＝U であ
るようなものである。
最大鎖は、ｎ！個ある。
実際に、１個の要素（例えば、ａ）を持つ部分集合の選び方は、ｎ
通り
ａ を含み、２個の要素を持つ部分集合の選び方は、ｎ−１
通り
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
以上から、 ｎ（ｎ−１）・・・２・１＝ｎ！（個）である。
A⊂Uで、Aの要素の数が r であれば、Aを含む最大鎖の数は、ｒ！(ｎ−ｒ)！である。
実際に、要素の個数が ｒ の部分集合の選び方は、ｎＣｒ 通りで、その１通りに対して、その
部分集合を含む最大鎖の数を Ｎ とすると、 ｎＣｒ×Ｎ＝ｎ！ が成り立つ。
よって、 Ｎ＝ｎ！÷ｎＣｒ＝ｒ！（ｎ−ｒ）！ となる。
AとBの間に包含関係がないなら、Aを含む最大鎖とBを含む最大鎖は必ず異なる。
以上のことから次の補題が成り立つ。
補 題 Sperner's theoremと同じ仮定のもとで、A1、A2、･･･、Ak のうちで要素の
個数が r であるものの個数を s(r)
とすると、
Σs(r)/nＣr≦1 （ただし、Σは、ｒ＝１ から ｎ
までの和)
（証明） Ａｍの要素の個数が ｒ
だとすると、Ａｍを含む最大鎖は、ｒ！（ｎ−ｒ）！個ある。この
ようなＡｍが
ｓ(ｒ)個あるから、その和は、ｓ(ｒ)・ｒ！（ｎ−ｒ）！である。これを、ｒ＝１から
ｎ まですべて加えたものが最大鎖すべての個数
ｎ！以下だから、
Σｓ(ｒ)・ｒ！（ｎ−ｒ）！≦ｎ！
両辺をｎ！で割って、 Σｓ(ｒ)/nＣr≦１ となる。 （証終）
（Sperner's theoremの証明） ｍ＝[ｎ/２] とすると、 nＣm≧nＣｒ だから、
補題より、Σｓ(ｒ)/nＣm≦Σｓ(ｒ)/nＣr≦１
分母を払って、Σｓ(ｒ)≦nＣm Σs(r)＝ｋ だから、 ｋ≦nＣm （証終）
さらに、ＦＮさんからの続報です。（平成２３年１月１９日付け）
例題１２’は、Sperner の定理を証明することで、一応終わりですが、鳩ノ巣原理とは関係
がなくなってしまいます。もちろん、それでいいのですが、鳩ノ巣を作ること自体も面白そうで
す。
Sperner の定理の証明で、chain を鎖と書いたのですが、chain のままの方がよさそうなの
でそうします。鳩ノ巣を作るのは、次を示すことになります。
U＝{１，２，・・・，ｎ} の部分集合の全体を共通要素を持たない nＣm 個の chain の
和で表すことができる。ただし、ｍ＝[ｎ/２]
この形では数学的帰納法による証明は無理ですが、より強くして、symmetric chain に
変えれば証明できます。
（帰納法による証明では、弱い結果は証明できないのに強い結果は証明できるということが
ときどきあります。帰納法の仮定がある程度強くないとうまくいかないということです。）
ここで、 chain ： A1⊂A2⊂･･･⊂Aｔ において、
ｎ（A1）＋ｎ（Aｔ）＝ｎ で、 ｎ（Aｓ）＋１＝ｎ（Aｓ+1）
が成り立つとき、symmetric chain という。ただし、ｎ（Ｘ）は、集合Ｘの要素の個数。
例 ｎ＝４ のときの鳩ノ巣を、symmetric chain で作れば、
Ｂ1 ： φ⊂{１}⊂{１，２}⊂{１，２，３}⊂{１，２，３，４}
Ｂ2 ： {２}⊂{２，３}⊂{２，３，４}
Ｂ3 ： {３}⊂{１，３}⊂{１，３，４}
Ｂ4 ： {４}⊂{１，４}⊂{１，２，４}
Ｂ5 ： {２，４}
Ｂ6 ： {３，４}
定 理
U＝{１，２，・・・，ｎ} の部分集合の全体を共通要素を持たない symmetric
chain の
和で表すことができる。
（証明） ｎ に関する数学的帰納法による。
ｎ＝１ のときは、 φ⊂{１} で成り立つ。
ｎ＝ｍ のとき、成り立つと仮定する。すなわち、U＝{１，２，・・・，ｍ}
の部分集合全体が共
通要素を持たない symmetric chain Ｂ1、Ｂ2、・・・、Ｂｋの和で表されるものとする。
このとき、Ｖ＝{０，１，２，・・・，ｍ} について考える。
Ｂｓ が、 Ｃ1⊂Ｃ2⊂･･･⊂Ｃt だとして、Ｖにおける２つの chain Ｂ’ｓ、Ｂ”ｓ を次の様に
定める。
Ｂ’ｓ ： Ｃ1⊂Ｃ2⊂･･･⊂Ｃt⊂Ｃt∪{０}
Ｂ”ｓ ： Ｃ1∪{０}⊂Ｃ2∪{０}⊂･･･⊂Ｃt-1∪{０}
（ただし、Ｂ”ｓは、Ｂｓの長さが２以上のときのみ）
Ｂ’ｓ、Ｂ”ｓ は、symmetric chain であり、これらの全体(ｓ＝１，２，・・・，ｋ）は共通要素を持
たずすべてのＶの部分集合を含む。
よって、ｎ＝ｍ＋１ のときも成り立ち、数学的帰納法により、定理は成り立つ。 （証終）
例 ｎ＝４ のときの symmetric chain から、ｎ＝５ のときの symmetric chain は、上の証
明に従って次のように作られる。
Ｂ1 ： φ⊂{１}⊂{１，２}⊂{１，２，３}⊂{１，２，３，４}
→ Ｂ’1 ： φ⊂{１}⊂{１，２}⊂{１，２，３}⊂{０，１，２，３，４}
→ Ｂ”1 ： {０}⊂{０，１}⊂{０，１，２}⊂{０，１，２，３}
Ｂ2 ： {２}⊂{２，３}⊂{２，３，４}
→ Ｂ’2 ： {２}⊂{２，３}⊂{０，２，３，４}
→ Ｂ”2 ： {０，２}⊂{０，２，３}
Ｂ3 ： {３}⊂{１，３}⊂{１，３，４}
→ Ｂ’3 ： {３}⊂{１，３}⊂{０，１，３，４}
→ Ｂ”3 ： {０，３}⊂{０，１，３}
Ｂ4 ： {４}⊂{１，４}⊂{１，２，４}
→ Ｂ’4 ： {４}⊂{１，４}⊂{０，１，２，４}
→ Ｂ”4 ： {０，４}⊂{０，１，４}
Ｂ5 ： {２，４}
→ Ｂ’5 ： {０，２，４}
Ｂ6 ： {３，４}
→ Ｂ’6 ： {０，３，４} （Ｂ”5 、Ｂ”6 はない。）
symmetric chain は、要素が、ｍ＝[ｎ/２]個の部分集合を必ず含むので、 ｋ≧nＣm
また、Sperner's theorem より、ｋ≦nＣm なので、 ｋ＝nＣm が成り立つ。
（コメント） ｎ＝４のときの鳩の巣は、4Ｃ2＝６（個）、
ｎ＝５のときの鳩の巣は、5Ｃ2＝１０（個）
の合点がいきました。ＦＮさんに感謝します。
攻略法さんが、反例となる豆をまいて鳩を集められました。（平成２３年１月２０日付け）
ｎ が大きいと、nＣｋ が天文学的数値になるということで、小さい値での調査とのことです。
２ｎ個の部分集合 Ｓｍ （０≦ｍ≦２ｎ−１）とする。（ｍのビットパターンでＳｍは展開する）
ｋ＝ｎＣ[ｎ/2] で命題を満たさない A1、A2、･･･、Ak の例は、
ｎ が偶数なら、「要素の個数が[ｎ/２]の Ｓｍ （個数は、ｎＣ[ｎ/2] 個）」の１通り
ｎ が奇数なら、「要素の個数が[ｎ/２]の Ｓｍ 」と
「要素の個数が[ｎ/２]＋１の Ｓｍ （個数は、ｎＣ[ｎ/2]+1個）」の２通り
例えば、ｎ＝２ の場合、部分集合は、２2＝４個
すなわち、 Ｓ0＝φ 、Ｓ1＝｛１｝ 、 Ｓ2＝｛２｝ 、 Ｓ3＝｛１，２｝
このとき、求める組は、Ｓ1＝｛１｝、Ｓ2＝｛２｝ の１通り
ｎ＝３ の場合、部分集合は、２3＝８個
すなわち、 Ｓ0＝φ 、Ｓ1＝｛１｝ 、 Ｓ2＝｛２｝ 、 Ｓ3＝｛１，２｝ 、
Ｓ4＝｛３｝ 、Ｓ5＝｛１，３｝ 、 Ｓ6＝｛２，３｝ 、 Ｓ7＝｛１，２，３｝
このとき、求める組は、
Ｓ1＝｛１｝、Ｓ2＝｛２｝、Ｓ4＝｛３｝
および
Ｓ3＝｛１，２｝、Ｓ5＝｛１，３｝、Ｓ6＝｛２，３｝ の２通り
ｎ＝４ の場合、部分集合は、２4＝１６個
すなわち、
Ｓ0＝φ 、Ｓ1＝｛１｝ 、 Ｓ2＝｛２｝ 、 Ｓ3＝｛１，２｝ 、
Ｓ4＝｛３｝ 、Ｓ5＝｛１，３｝ 、 Ｓ6＝｛２，３｝ 、 Ｓ7＝｛１，２，３｝、
Ｓ8＝｛４｝ 、Ｓ9＝｛１，４｝ 、 Ｓ10＝｛２，４｝ 、 Ｓ11＝｛１，２，４｝ 、
Ｓ12＝｛３，４｝ 、Ｓ13＝｛１，３，４｝ 、 Ｓ14＝｛２，３，４｝ 、 Ｓ15＝｛１，２，３，４｝
このとき、求める組は、
Ｓ3＝｛１，２｝、Ｓ5＝｛１，３｝、Ｓ6＝｛２，３｝、
Ｓ9＝｛１，４｝、Ｓ10＝｛２，４｝、Ｓ12＝｛３，４｝ の１通り
例題１３ １ から ４ までの自然数からいくつか選んで作った９個の集合 Ａ1、Ａ2、・・・、Ａ9
がすべて異なるとき、Ａｍ∩Ａｎ＝φ となる Ａｍ 、 Ａｎ が存在する。
（解） 集合 ｛ １ ， ２ ， ３ ， ４ ｝ の部分集合は全部で、２4＝１６個ある。
それらを列挙すると、、
φ、｛ １ ｝、｛ ２ ｝、｛ ３ ｝、｛ ４ ｝、｛ １ ， ２ ｝、｛
１ ， ３ ｝、｛ １ ， ４ ｝、｛ ２ ， ３ ｝、
｛ ２ ， ４ ｝、｛ ３ ， ４ ｝、｛ １ ， ２ ， ３ ｝、｛ １
， ２ ， ４ ｝、｛ １ ， ３ ， ４ ｝、
｛ ２ ， ３ ， ４ ｝、｛ １ ， ２ ， ３ ， ４ ｝
これらを、どの２つも共通部分がないように分類すると、
Ｂ1 ： φ と ｛ １ ， ２ ， ３ ， ４ ｝
Ｂ2 ： ｛ １ ｝ と ｛ ２ ， ３ ， ４ ｝
Ｂ3 ： ｛ ２ ｝ と ｛ １ ， ３ ， ４ ｝
Ｂ4 ： ｛ ３ ｝ と ｛ １ ， ２ ， ４ ｝
Ｂ5 ： ｛ ４ ｝ と ｛ １ ， ２ ， ３ ｝
Ｂ6 ： ｛ １ ， ２ ｝ と ｛ ３ ， ４ ｝
Ｂ7 ： ｛ １ ， ３ ｝ と ｛ ２ ， ４ ｝
Ｂ8 ： ｛ １ ， ４ ｝ と ｛ ２ ， ３ ｝
の８個（これが、鳩ノ巣）に分けられる。
これに対して、９個の集合 Ａ1、Ａ2、・・・、Ａ9 がある（これが、鳩）ので、ある Ｂｋ に
少なくとも２つ Ａｍ 、 Ａｎ が含まれ、Ａｍ∩Ａｎ＝φ が成り立つ。（終）
ＦＮさんが、この問題を一般化された。（平成２３年１月１５日付け）
例題１３’ １から ｎ までの自然数からいくつか選んで作った ｋ 個の集合 Ａ1、Ａ2、・・・、Ａｋ
がすべて異なるとき、Ａｍ∩Ａｎ＝φ となる Ａｍ 、 Ａｎ が存在する。
自然数 ｎ が与えられたとき、この命題が成り立つような自然数
ｋ の最小値を
求めよ。
これについて、一般の ｎ だと雲を掴むような話のような．．．雰囲気なので、例題１２’と
同様に、ｎ＝５ として実験してみた。
集合 ｛ １ ， ２ ， ３ ， ４， ５ ｝ の部分集合は全部で、２5＝３２個ある。
それらを列挙すると、、
φ、｛ １ ｝、｛ ２ ｝、｛ ３ ｝、｛ ４ ｝、｛ ５ ｝、｛ １ ， ２ ｝、｛
１ ， ３ ｝、｛ １ ， ４ ｝、｛ １ ， ５ ｝、
｛ ２ ， ３ ｝、｛ ２ ， ４ ｝、｛ ２ ， ５ ｝、｛ ３ ， ４ ｝、｛ ３
， ５ ｝、｛ ４ ， ５ ｝、｛ １ ， ２ ， ３ ｝、
｛ １ ， ２ ， ４ ｝、｛ １ ， ２ ， ５ ｝、｛ １ ， ３ ， ４ ｝、｛
１ ， ３ ， ５ ｝、｛ １ ， ４ ， ５ ｝、
｛ ２ ， ３ ， ４ ｝、｛ ２ ， ３ ， ５ ｝、｛ ２ ， ４ ， ５ ｝、｛
３ ， ４ ， ５ ｝、｛ １ ， ２ ， ３ ， ４ ｝、
｛ １ ， ２ ， ３ ， ５ ｝、｛ １ ， ２ ， ４ ， ５ ｝、｛ １ ， ３ ，
４ ， ５ ｝、｛ ２ ， ３ ， ４ ， ５ ｝、
｛ １ ， ２ ， ３ ， ４， ５ ｝
これらを、どの２つも共通部分がないように分類すると、
Ｂ1 ： φ と ｛ １ ， ２ ， ３ ， ４， ５ ｝
Ｂ2 ： ｛ １ ｝ と ｛ ２ ， ３ ， ４ ， ５ ｝
Ｂ3 ： ｛ ２ ｝ と ｛ １ ， ３ ， ４ ， ５ ｝
Ｂ4 ： ｛ ３ ｝ と ｛ １ ， ２ ， ４ ， ５ ｝
Ｂ5 ： ｛ ４ ｝ と ｛ １ ， ２ ， ３ ， ５ ｝
Ｂ6 ： ｛ ５ ｝ と ｛ １ ， ２ ， ３ ， ４ ｝
Ｂ7 ： ｛ １ ， ２ ｝ と ｛ ３ ， ４ ， ５ ｝
Ｂ8 ： ｛ １ ， ３ ｝ と ｛ ２ ， ４ ， ５ ｝
Ｂ9 ： ｛ １ ， ４ ｝ と ｛ ２ ， ３ ， ５ ｝
Ｂ10 ： ｛ １ ， ５ ｝ と ｛ ２ ， ３ ， ４ ｝
Ｂ11 ： ｛ ２ ， ３ ｝ と ｛ １ ， ４ ， ５ ｝
Ｂ12 ： ｛ ２ ， ４ ｝ と ｛ １ ， ３ ， ５ ｝
Ｂ13 ： ｛ ２ ， ５ ｝ と ｛ １ ， ３ ， ４ ｝
Ｂ14 ： ｛ ３ ， ４ ｝ と ｛ １ ， ２ ， ５ ｝
Ｂ15 ： ｛ ３ ， ５ ｝ と ｛ １ ， ２ ， ４ ｝
Ｂ16 ： ｛ ４ ， ５ ｝ と ｛ １ ， ２ ， ３ ｝
の１６個（これが、鳩ノ巣）に分けられる。
したがって、鳩ノ巣原理を用いて、ある Ｂｋ に少なくとも２つ Ａｍ 、 Ａｎ が含まれ、
Ａｍ∩Ａｎ＝φ が成り立つようにするためには、最低１７個の集合 Ａ1、Ａ2、・・・、Ａ17 （これ
が、鳩）があればよい。
よって、 ｎ＝５ のとき、 ｋ＝１7 である。
ｎ＝４ のとき、 ｋ＝９ であるわけだが、次のような規則性があるような．．．予感。
任意に与えられた自然数 ｎ に対して、命題が成り立つような自然数 ｋ の最小値は、
ｋ＝２ｎ-1＋１
である。
FNさんからのコメントです。（平成２３年１月１７日付け）
これが一番簡単でしょう。２n-1個の鳩の巣があることを示すのは、例題１２’のように難し
くないと思います。
ＦＮさんからの補足です。（平成２３年１月２０日付け）
例題１２’の解答の対偶的表現が、Sperner の定理ですが、例題１３’の解答の対偶的表
現は次のようになります。
ｎ 個の要素を持つ集合Uの部分集合の族 Ａ1、Ａ2、・・・、Ａｋ がどの２つを取っても
共通部分が空集合でないとき、 ｋ≦２n-1 である。
これは、Sperner の定理と違ってほとんど明らかです。
（証明） Ａとその補集合Ａ’は共通部分が空集合だから、どちらか一方しか部分集合の族
には入れない。従って、部分集合の個数は、２ｎ の半分以下である。 （証終）
攻略法さんが、反例となる豆をまいて鳩を集められました。（平成２３年１月２０日付け）
ｎ が大きいと、nＣｋ が天文学的数値になるということで、小さい値での調査とのことです。
ｋ＝２n-1 で命題を満たさない Ａ1、Ａ2、・・・、Ａｋ の例は、ｎ によって個数は違うが、その
２例は、「 Ｓｍ が奇数列」または「 Ｓｍ が最後からｋ個」となる。
（ただし、ｍのビットパターンでＳｍは展開する）
ｎ＝２ の場合 Ｓ0＝φ 、Ｓ1＝｛１｝ 、 Ｓ2＝｛２｝ 、 Ｓ3＝｛１，２｝
求める組は、 Ｓ1＝｛１｝、Ｓ3＝｛１，２｝ および Ｓ2＝｛２｝、Ｓ3＝｛１，２｝ の２通り
ｎ＝３ の場合 Ｓ0＝φ 、Ｓ1＝｛１｝ 、 Ｓ2＝｛２｝ 、 Ｓ3＝｛１，２｝ 、
Ｓ4＝｛３｝ 、Ｓ5＝｛１，３｝ 、 Ｓ6＝｛２，３｝ 、 Ｓ7＝｛１，２，３｝
求める組は、 Ｓ1＝｛１｝、Ｓ3＝｛１，２｝、Ｓ5＝｛１，３｝、Ｓ7＝｛１，２，３｝
および、
Ｓ4＝｛３｝、Ｓ5＝｛１，３｝、Ｓ6＝｛２，３｝、Ｓ7＝｛１，２，３｝
その他、 Ｓ2、Ｓ3、Ｓ6、Ｓ7 および Ｓ3、Ｓ5、Ｓ6、Ｓ7
同様に、ｎ＝４ の場合
Ｓ1、Ｓ3、Ｓ5、Ｓ7、Ｓ9、Ｓ11、Ｓ13、Ｓ15 を、(1,3,5,7,9,11,13,15) と略記して、求める組は
(1,3,5,7,9,11,13,15) および (8,9,10,11,12,13,14,15)
その他、 (2,3,6,7,10,11,14,15)、(3,5,6,7,11,13,14,15)、(3,5,7,9,11,13,14,15)、
(3,6,7,10,11,13,14,15)、(3,7,9,10,11,13,14,15)、(4,5,6,7,12,13,14,15)、
(5,6,7,11,12,13,14,15)、(5,7,9,11,12,13,14,15)、(5,7,9,11,12,13,14,15)、
(6,7,10,11,12,13,14,15)、(7,9,10,11,12,13,14,15)
（コメント） 攻略法さん、具体的な例をたくさん計算していただいて感謝します。
例題１４ １ から ４ までの自然数から２つを選んで作った４個の集合 Ａ1、Ａ2、Ａ3、Ａ4 が
すべて異なるとき、Ａｍ∩Ａｎ＝φ となる Ａｍ 、 Ａｎ が存在する。
（解） １ から ４ までの自然数から２つを選んで作った集合を列挙すると、、
｛ １ ， ２ ｝、｛ １ ， ３ ｝、｛ １ ， ４ ｝、｛ ２ ， ３
｝、｛ ２ ， ４ ｝、｛ ３ ， ４ ｝
の６個ある。これらを、どの２つも共通部分がないように分類すると、
Ｂ1 ： ｛ １ ， ２ ｝ と ｛ ３ ， ４ ｝
Ｂ2 ： ｛ １ ， ３ ｝ と ｛ ２ ， ４ ｝
Ｂ3 ： ｛ １ ， ４ ｝ と ｛ ２ ， ３ ｝
の３個（これが、鳩ノ巣）に分けられる。
これに対して、４個の集合 Ａ1、Ａ2、Ａ3、Ａ4 がある（これが、鳩）ので、ある Ｂｋ に
少なくとも２つ Ａｍ 、 Ａｎ が含まれ、Ａｍ∩Ａｎ＝φ が成り立つ。（終）
ＦＮさんが、この問題の一般化を考えられた。（平成２３年１月２０日付け）
例題１４の自然な一般化は、１から４までの４を２ｎに、２つをｎ個に、４個を2nＣn/２＋１個
に変えることで、これなら鳩ノ巣原理を使った証明がそのままできます。
ただし、2nＣn/２＝2n-1Ｃn-1 である。
もっと一般にすることを考えます。ただしそうなると鳩ノ巣原理は使えそうな気はしません。
鳩ノ巣原理が使えないとすると、対偶的表現の方が自然かなと思います。
例題１４’ ｎ 個の要素を持つ集合Uがある。ｋ個からなるUの部分集合の族
Ａ1、Ａ2、・・・、Ａｋ （すべて異なる）で、次の条件を満たすものが存在するとき、
ｋ の最大値を求めよ。
（１） 任意の ｔ について、Ａｔ の要素の個数は、ｍ
（２） 任意の ｓ、ｔ （ｓ≠ｔ）について、 Ａｓ∩Ａｔ≠φ
この問題は、「自然数 ｎ、ｍ が与えられたとき、ｋ の最大値を求めよ」ということです。
２ｍ＞ｎ であれば、（２）は常に成り立つので、ｍ個の要素をもつ部分集合全体が条件を
満たし、nＣm が答えになります。だから、２ｍ≦ｎ としておきます。
因みに、２ｍ＝ｎ のときは、上に書いた自然な一般化の場合です。
ｍ＝１ のときは、当然、ｋ＝１ です。ｍ＝２、ｍ＝３ の場合はどうなるでしょうか？
ＦＮさんの問いかけに対して、ＨＮ「ａｔ」さんが答えられた。（平成２３年１月２１日付け）
これは、Ｅｒｄｏｓ-Ｋｏ-Ｒａｄｏ Ｔｈｅｏｒｅｍ で、ｋ の最大値は、 ｎ-1Ｃｍ-1 です。
ＦＮさんからのコメントです。（平成２３年１月２１日付け）
やはり、綺麗な解答が既に得られているのですね。Erdos-Ko-Radoの論文が１９６１年だ
そうで、実際には、その二十年以上前に証明されていたそうですが、それにしても、かなり
新しい結果です。
Spernerの定理が１９２８年らしいので、これもかなり新しい結果です。もっとも、集合という
ようなものが研究対象となったこと自体が20世紀に入る前後なのかもしれませんが．．．。
上のWikipediaの証明を読んでみましたが理解できませんでした。Erdos-Ko-Radoの原論
文はもっと一般的な形の定理でこれも理解できません。他にもいろいろな証明があるようで
すが、できるだけ簡単な証明を知りたいです。
ａｔ さんが、「Erdos-Ko-Rado theorem の証明」を与えられた。（平成２３年１月２２日付け）
（証明） ｎ個の整数 １、２、・・・、ｎ の任意の順列 π＝（ａ1、ａ2、・・・、ａｎ）を考える。
ある円周上の１点に赤い印をつけておき、この赤い印を出発点として、ａ1、ａ2、・・・、ａｎ
をこの順に円周上に反時計回りに書き込む。この円上で、隣り合うｍ個の数を ｍ-ブロック
と呼ぶことにする。(ｍ-ブロックは、全部で ｎ 種類あることになる。)
あるひとつの ｍ-ブロックに含まれるｍ個の数が、 Ａ1、Ａ2、・・・、Ａｋ のどれかと一致する
とき、このｍ-ブロックを「良いｍ-ブロック」と呼ぶことにする。
さらに、任意の順列πに対して、良いｍ-ブロックの総数を N(π) で表すことにする。
このとき、任意の順列πに対して、N(π)≦ｍ が成り立つ。
実際に、もし、N(π)＞ｍ とすると、共通点を持たないような２つの良いｍ-ブロック
が存
在することになる。しかし、これは、 Ａｓ∩Ａｔ≠φ という仮定に反する。
（ 例： ｎ＝４ 、ｍ＝２ とする。 Ｕ＝｛１，２，３，４｝の部分集合
Ａ1＝｛１，２｝、Ａ2＝｛２，３｝、Ａ3＝｛３，４｝
順列 π＝（３、１、２、４）に対して、良い２-ブロックとして、（１，２）、（４，３）の２つ
順列 π＝（３、１、４、２）に対して、良い２-ブロックとして、（２，３）の１つ
この例からも、 N(π)≦ｍ が納得される。 ）
πがすべての順列を動くとき、良いｍ-ブロックが合計何回現れるのかをカウントする。
ある Ａｔ に一致するような良いｍ-ブロックは、それが円周上のどの位置に出現するのか
を考えれば、ｎ 通りの方法がある。さらに、このｍ-ブロックには、ｍ個の数があるので、こ
のｍ個の数の順列を考えることにより、ｍ！通りの方法がある。
さらに、このｍ-ブロックに含まれない数が ｎ−ｍ 個あるので、これらの数の順列を考え
ることにより、（ｎ−ｍ）！通りの方法がある。
以上より、πがすべての順列を動くとき、ある Ａｔ に一致するような良いｍ-ブロックは、
ｎ・ｍ！・（ｎ−ｍ）！（回）
だけ出現する。
よって、πがすべての順列を動くとき、良いｍ-ブロックの出現総数は、
ΣN(π)＝ｋ・ｎ・ｍ！・（ｎ−ｍ）！（回） （Σは全ての順列
π にわたる）
となる。
ここで、 ΣN(π)≦ｍ・ｎ！ なので、 ｋ・ｎ・ｍ！・（ｎ−ｍ）！≦ｍ・ｎ！
したがって、 ｋ≦ｎ-1Ｃｍ-1 である。 （証終）
ＦＮさんからのコメントです。（平成２３年１月２２日付け）
有難うございます。あちこち見てもわからなかったのが何とか理解できたと思います。日
本語と英語の違いもあり、今までにあちこち見てある程度状況に入れてたこともありますが
ａｔ さんの説明が良かったので理解できました。「N(π)≦ｍ」に当たる部分が理解できず、
そこで思考停止を起こしていました。わかった後で見れば、N(π)≦ｍ は明らかと言ってい
いぐらいでした。