鳩ノ巣原理 
高校で習う論証法としては、「背理法」や「数学的帰納法」が有名である。「平方根２
が無理
数である」ことを示すのに、背理法が使われるが、大学入試における、その他もろもろの問
題においても、背理法が登場する頻度は高い。また、自然数 ｎ に関する命題の証明には、
数学的帰納法が活躍する。「自然数 ｎ に対して、２n＞ｎ 」を示す場合、直接的な証明も可
能であるが、数学的帰納法による証明の方が簡明である。
結論を否定して、矛盾を導くという背理法の証明方法は、新しい数学の定理を創造するの
に有効である。いくつか具体的な事例を計算して結論の予想を立て、それを証明する場合、
背理法が主に使われる。大学院時代、同じ研究室にいらした、群論を専門とする方に論文
を見せてもらう機会があったが、ほとんど背理法一色であった。それだけ、背理法は数学的
な論証において、強力な武器となりうる。
この「背理法」や「数学的帰納法」に匹敵すると思われる、論証の武器 ：「鳩ノ巣原理」は、
なぜかしら高校で教えられることはない。しかし、数学オリンピックの必須アイテムであるこ
とを考えると、世界の標準的な論証法と考えるべきだろう。鳩ノ巣原理は、存在定理を証明
するときに有効である。
鳩ノ巣原理について最初に言及したのは、ドイツの数学者ヨハン・ディリクレ（１８３４年）で、
「引き出し論法」という言葉を使っている。「鳩ノ巣原理」というフレーズを数学の専門誌で最
初に使ったのは、数学者のラファエル・Ｍ・ロビンソン（１９４０年）と言われる。
「鳩ノ巣原理」を意識するには、次の問題を考えるといいだろう。
問題 サイコロ１個を何回続けて投げるかを予め宣言する。
宣言した回数以内に同じ目が２回以上出たら、「勝ち」
そうならなかったら、「負け」
さて、あなたは何回と宣言すれば、必ず勝てるでしょうか。最小回数を答えてください。
正解は、「７回」です。これは何故？と思われた方は是非「鳩ノ巣原理」を学んでください。
そして、上記のような問題が自由に作れたら、あなたはもう鳩ノ巣原理マスターですね！
鳩ノ巣原理自体は、とても当たり前のことを主張する。
鳩ノ巣原理（・・・ディリクレの引き出し論法、部屋割り論法ともいわれる）
ｎ 個の巣穴に ｎ＋１ 羽の鳩を入れる場合、
必ずどれかの巣穴は、２ 羽以上
これを一般化して、
ｎ 個の巣穴に ｍ 羽の鳩を入れる場合、ｍ＞ｋｎ ならば、
必ずどれかの巣穴は、ｋ＋１ 羽以上
|
 |
「たくさんあるものの中で、２つ（以上）は同じ」ことを示したりする場合、鳩ノ巣原理がよく
用いられる。
上記の問題だと、サイコロの目は、１〜６の６個なので、７回と宣言すれば、必ずどれかの
目が２回以上出ることは確実なので、「勝ち」となる。
さらに、次の問題に対して、この鳩ノ巣原理を応用してみよう。
問題 実数係数の３次方程式が次の性質を持つとする。
α が解ならば、その平方 α2 も解になる
このとき、この性質を持つ３次方程式の解の絶対値は、０ または １ である。
（解） 今 α が解ならば、α2、α4、α8 も解になる。ところが、３次方程式は、３個の解しか
もたないので、α、α2、α4、α8 のうち相等しいものが存在する。（鳩ノ巣原理）
そこで、ある ｍ、ｎ に対して、αｍ＝αｎ （ｍ＞ｎ）とすると、
αｎ（αｍ−ｎ−１）＝０
から、｜α｜ｎ＝０、｜α｜ｍ−ｎ＝１ となり、｜α｜＝０、１ が成り立つ。（終）
この問題からも分かるように、何が鳩ノ巣で、何が鳩かを把握することが、この論法のキ
ーポイントである。上記問題では、３個の解が鳩ノ巣で、４つの数 α、α2、α4、α8 が鳩に
相当する。
鳩ノ巣原理は、その単純さから、一般の人にとっても納得されやすい原理であるが、実際
に、問題解決に利用しようとする場合、相当の熟練を要する。このページでは、鳩ノ巣原理
を利用する問題をいくつか提示して、その適用の仕方を見ていこう。これらの例題をマスタ
ーすれば、無意識の内に「鳩ノ巣原理」が使えるようになるだろう。
例題１ 分数を小数に直す場合、有限小数か、循環小数である。これは、どうしてか？
（解） 分子を分母で割り算したとき、割り切れれば、有限小数である。割り切れず、永
遠に割り算が繰り返される場合に、循環小数ができる。
実際に、分母 ｎ で割ったとき、その余りの可能性は、１、２、３、・・・、ｎ−１
の
ｎ−１ 個ある。（これが、鳩ノ巣）
今、ｎ 回割り算を繰り返して、余りが、ｎ 個得られたとする。（これが、鳩）
このとき、鳩ノ巣原理により、この余りのうち、少なくとも２つは同じ数である。
よって、その同じ数に対応するところから、小数は循環する。（終）
例題２ １辺が ４ の正方形の内部および辺上に、９つの点をとる。このうちの３点を結ん
で三角形を作るとき、すくなくとも一つの三角形の面積は、２ 以下である。
（解） 与えられた正方形の各辺の中点を結んで、４つの合同な正方形に分割する。（こ
れが、鳩ノ巣） いま、９つの点（これが、鳩）があるので、鳩ノ巣原理により、
９＞２×４ から、少なくとも一つの三角形の内部および辺上に、２＋１＝３
個以上
の点がある。このうちの３点で作られる三角形の面積は、２ 以下である。（終）
（ものの本によると、このような三角形は、少なくとも２個あるらしい！）
例題３ １辺が ２ の正三角形の内部および辺上に、５つの点をとる。このとき、２点間の
距離が １ 以下であるような２点が存在する。
（解） 与えられた正三角形の各辺の中点を結んで、４つの合同な正三角形に分割する。
（これが、鳩ノ巣） いま、５つの点（これが、鳩）があるので、鳩ノ巣原理により、ど
れか１つの正三角形の内部および辺上に、２つ以上の点がある。このうちの２点を
結んで得られる線分の長さは、１ （正三角形の一辺の長さ）以下である。（終）
例題４ ３で割って １ 余る数の数列： １，４，７，・・・，９７，１００ を考える。この３４個の数
から相異なる ２０ 個の数をどのように選んでも必ず、その ２０ 個の中に、２つの相
異なる数で、和が、１０４ となるものが存在する。
（解） 和が、１０４ となる数の組合せは、
４＆１００、７＆９７、１０＆９４、・・・、４９＆５５ の１６ 通りある。この各場合に使わ
れていない数は、１ と ５２ である。そこで、次の １８ 通りの場合を考える。
４＆１００、７＆９７、１０＆９４、・・・、４９＆５５、１、５２ （これが、鳩ノ巣）
今、相異なる ２０ 個の数を任意に選ぶ。（これが、鳩）
このとき、鳩ノ巣原理により、２つの数とも選ばれている対 Ａ＆Ｂ
が存在して、
Ａ＋B＝１０４ である。（終）
＃「和が、104となる数の組合せ」に誤りがあると、Kelly Burkhard さんからご指摘いただきまし
た。（平成３０年８月１１日付け） 上記は修正済みです。Kelly Burkhard さんに感謝します。
例題５ １ から １９９９ までの１０００個の奇数がある。この中から、 ５０１個の奇数をどの
ように選んでも必ず、その ５０１ 個の中に、２つの相異なる数で、和が、２０００
とな
るものが存在する。
（解） 和が、２０００ となる数の組合せは、
１＆１９９９、３＆１９９７、５＆１９９５、・・・、９９９＆１００１ の５００
通りある。（これ
が、鳩ノ巣） 今、相異なる ５０１ 個の奇数を任意に選ぶ。（これが、鳩）
このとき、鳩ノ巣原理により、２つの数とも選ばれている対 Ａ＆Ｂ
が存在して、
Ａ＋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(π)≦ｍ は明らかと言ってい
いぐらいでした。
例題１５ タンスの中に３種類の靴下が１足ずつ入っている。このとき、手探りで、１足を
揃えるにはタンスから何本とればいいか？
（解） ４本とれば必ず１足はできる。
Kelly Burkhard さんからのコメントです。（平成３０年８月１１日付け）
同じ鳩ノ巣原理を使う問題でもバリエーションがあるのだなと思いました。何が違うのかは
まだ分かりやすく表現できていませんが．．．。例題１５は純粋な鳩ノ巣原理だと感じました。
鳩ノ巣原理では「巣穴」の設定が重要で、別の巣穴に同じ「鳩」が入らないように、「巣穴」
に入れない「鳩」がいないように巣穴を設定しなければならないということに気づきました。
次の問題は鳩ノ巣原理の匂いが感じられないかもしれないが、立派な鳩ノ巣原理の問題
です。
例題１６ ３ｍ×３ｍの土地に木を１０本植える。このとき、どの２本も１．５ｍ以上離して
植えることは可能だろうか。
（解） ９本だったら可能だが、１０本では絶対不可能である。
実際に、３ｍ×３ｍの土地を１ｍ×１ｍの土地９区画（これが、鳩ノ巣）に分けるとき、
１０本の木（これが、鳩）が植えられるとすると、必ず少なくとも２本は、ある一つの区
画内にある。その距離は、最大で
＝１．４１４・・・＜１．５ なので条件に反する。
例題１７ １から２０までの自然数の中から、互いに他で割り切れないように、１０個の数を
選べ。また、１１個では、そのような選び方は不可能であることを示せ。
（解） １は全ての数の約数なので、選べない。２を選ぶと、選ばれる候補は、
３、５、７、９、１１、１３、１５、１７、１９ の奇数 ９個
この中で、３と９、３と１５、５と１５は条件に反するので、１０個の数を選ぶことは不可能。
３を選ぶと、３の倍数の ６、９、１２、１５、１８ は選べないので、
４、５、７、８、１０、１１、１３、１４、１６、１７、１９、２０ の１２個から９個を選ぶわけであるが、
４、８、１６、２０ ５、１０、２０ ７、１４
は一緒に選べないので、９個を選ぶことは不可能。
５を選ぶと、５の倍数 １０、１５、２０ は選べないので、
６、７、８、９、１１、１２、１３、１４、１６、１７、１８、１９ の１２個から９個を選ぶわけであるが、
６、１２、１８ ７、１４ ８、１６ ９、１８
は一緒に選べないので、９個を選ぶことは不可能。
６を選ぶと、６の倍数 １２、１８ は選べないので、
７、８、９、１０、１１、１３、１４、１５、１６、１７、１９、２０ の１２個から９個を選ぶわけである
が、６の代わりに１２、７の代わりに１４、８の代わりに１６、９の代わりに１８、１０の代わりに
２０を選ぶことにすれば、１１、１２、１３、１４、１５、１６、１７、１８、１９、２０ の１０個の数が
条件を満たす。
実際に、この１０個の数が条件を満たすことを検証してみよう。
この１０個の中に互いに他で割り切れるような組 ａ、ｂ（１１≦ａ＜ｂ≦２０）が存在したとする
と、ｂがａで割り切れるので、ｂ＝ｋａ （ｋは自然数） と書ける。
このとき、ｋ≧２ で、ａ≧１１ より、 ｂ≧２２ となり、ｂ≦２０ であることに矛盾。
よって、この１０個の中には互いに他で割り切れるような組 ａ、ｂ は存在しない。
それでは、１１個では、そのような選び方は不可能であることをどう示せばいいのでしょう。
それを示すために、鳩ノ巣原理が有効に活躍します。
１から２０までの自然数の中から、互いに他で割り切れないような１１個の数（これが、鳩）
が任意に選ばれたものとする。この数のうち、１〜１０までの数を、２倍、２倍、・・・を繰り返
すことにより、１１〜２０の数（これが、鳩ノ巣）にすることができる。このとき、鳩ノ巣原理に
より、１１〜２０のある数Ｎについて、
Ｎ＝ｘ・２ｎ＝ｙ・２ｍ （ただし、ｘ＜ｙ で、さらに、ｍ、ｎは整数で、ｎ＞ｍ）
となるものが存在する。このとき、ｙ＝ｘ・２ｎ−ｍ と書くことができ、ｙがｘで割り切れることを
示している。これは、矛盾である。
よって、互いに他で割り切れないような１１個を選ぶことは、不可能である。 （終）
（コメント） 不可能性の証明は難しいと思いましたが、意外にあっさりで肩すかしを食らった
ような気分ですね！
上記の問題を一般化すると、
１から２ｎ （ｎ≧１）までの自然数の中から、互いに他で割り切れないように、ｎ個の
数を選ぶことは可能であるが、１１個では、そのような選び方は不可能である。
前半は、ｎ、ｎ＋１、・・・、２ｎ を選べばよい。後半は、上記と同様に示される。
DD++さんから、「オーレの定理」に関する話題をいただきました。
（平成２９年７月１１日付け）
例題１８（鳩ノ巣原理について、面白いものを1つ。）
10個の島があり、それらの間にいくつかの橋がかかっています。簡単のため、同じ２島間
に複数の橋がかかっていることはないとしましょう。
（それを許しても、まとめて1本と数えればいいだけで大差ありませんが．．．。）
この10島について、任意の２島の組を選んだときに、
「その２島間に橋がかかっている」
「その２島にかかっている橋の本数の和が10以上である」
のいずれか少なくとも一方が成り立つならば、全１０島をちょうど一度ずつ通って元の島に
戻ってくる巡回路が存在することが証明できます。
（証明） 背理法を用います。１０島から任意の２島の組を選んだときに、
「その２島間に橋がかかっている」
「その２島にかかっている橋の本数の和が１０以上である」
のいずれかが成り立っているにも関わらず、全１０島を一度ずつ通って元の島に戻ってくる
巡回路が存在しなかったと仮定します。
間に橋がかかっていない２島を選び、橋を１つ建設します。これで巡回路ができればそこ
でストップ、できなければ再び間に橋がかかっていない２島を選び、橋を１つ建設、それを繰
り返して初めて巡回路が存在する状況になった状況について考えます。
最後に橋をかけた２つの島をＡおよびＪと名付けます。このＡＪ間の橋によって初めて巡回
路ができたので、今ある巡回路は全てこの橋を通ります。その巡回路のうちの１つを選び、
Ａから出発して最後にＪに着いてＡに戻るまで通る順に島の名前をＡ、Ｂ、Ｃ、・・・、Ｊとします。
さて、ＡとＪはもともと橋がかかっていなかった島の組なので、ＡＪ以外に少なくとも１０本、
ＡまたはＪからかかっている橋が存在します。ABとIJは当然橋がかかっているのでこれらも
除外すれば残り少なくとも8本。それがかかっている場所の候補１４箇所を
「ＡＣとＢＪ」、「ＡＤとＣＪ」、「ＡＥとＤＪ」、「ＡＦとＥＪ」、「ＡＧとＦＪ」、「ＡＨとＧＪ」、「ＡＩとＨＪ」
と、７組にグループ分けすると、鳩ノ巣原理より、少なくともどれか1つは実際に橋がかかって
いる２箇所の組になります。
例えば、それが「ＡＥとＤＪ」だったとしましょう。すると、これら２本の橋を利用して後半を逆
回りするABCDJIHGFEAという巡回路が存在します。
他の組でも同様に、その２本を利用して後半を逆回りする巡回路が存在しますが、いずれ
の場合でも、その巡回路の存在は、今ある巡回路は全てＡＪ間の橋を通ることに矛盾します。
したがって仮定は誤りであり、条件を満たす１０島には、必ず全１０島を一度ずつ通って元
の島に戻ってくる巡回路が存在することが示されました。
＃もちろんN(≧3)個の島で橋の本数の和をN以上とすれば一般に成り立ちます。
（オーレの定理）
例題１９ 相異なる７個の整数をどのように選んでも、その差または和が１０の倍数となる
２数が存在する。
（解） 相異なる７個の整数を１０で割った余りで分類すると、
０、１、２、３、４、５、６、７、８、９
の何れかになる。そこで、１０で割った余りが ｋ または １０−ｋ である集合をＡｋとす
ると、相異なる７個の整数（これが、鳩）は、
Ａ0、Ａ1、Ａ2、Ａ3、Ａ4、Ａ5
の何れかに属する。（これが、鳩ノ巣）
鳩ノ巣原理により、相異なる７個の整数のうちの２数を含むＡｋが存在する。
その２数を１０で割った余りが、ともに ｋ または、ともに １０−ｋ のとき、その２数の
差をとると、１０の倍数になる。
その２数を１０で割った余りが、一つは ｋ で他方が １０−ｋ のとき、その２数の和をと
ると、１０の倍数になる。 （終）
例題２０ １から１０までの自然数を並べた数列は、少なくとも４個の数からなる単調増加
列または単調減少列を含むことを示せ。
（例） 乱数表を使って、１から１０までの１０個の自然数を並べてみた。
９ 、１ 、２ 、４ 、８ 、５ 、７ 、６ 、３ 、１０
この自然数列に対して、 「１ 、２ 、４ 、８」が条件を満たす。どんな自然数列に対しても
このような数列が存在するところが面白い。
さて、どうやって示すのだろう。もちろん、鳩ノ巣原理を使う訳なのだが．．．。
この例題２０を一般化すれば、次の例題２０’が得られる。
例題２０’ １からｎ2＋１までの自然数を並べた数列は、少なくともｎ＋１個の数からなる単
調増加列または単調減少列を含むことを示せ。
DD++さんからのコメントです。（平成２９年７月１8日付け）
証明してみましたが、鳩ノ巣原理が登場しませんでした。あれぇー？鳩ノ巣原理を使うと、
もっとスパッといくのでしょうか。
（証明） まず、
「異なる実数を並べた数列に含まれる単調増加列または単調減少列が全て ｎ 個以下の
数からなるとき、数列の実数は、ｎ2個以下である」
を数学的帰納法で示します。
(i) n=1 のとき、
２個以上の数からなる単調増加列や単調減少列が存在しないことは、異なる２数が存在し
ないことを意味するので、項数は1以下であり、命題は成立します。
(ii) n=k のとき、命題が成立すると仮定して、n=k+1 のときを考えます。
この数列には、k+2個以上の数からなる単調減少列が存在しないことから、もし、k+1個の
数からなる単調減少列があれば、その先頭の数は、それより前にあるどの数よりも大きく
なければいけません。
そこで、この数列のうち、「その数はそれより前にあるどの数より大きい」を満たす数に赤
い印をつけます。
すると、もし、k+1個の数からなる単調減少列があれば、その先頭の数には赤い印がつい
ていることになります。
同様に、「その数はそれより後ろにあるどの数より大きい」を満たす数に青い印をつけると、
もし、k+1個の数からなる単調増加列があれば、その末尾の数には青い印がついていること
になります。
このとき、k+1個の数からなる単調増加列も単調減少列も印のついた数が必ず含まれるの
で、印が何もついていない数のみからなる単調増加列や単調減少列は全てk個以下の数か
らなります。
よって、帰納法の仮定より、印のない数はk^2個以下です。
また、赤い印をつけた数は単調増加列になっているので、赤い印のある数はk+1個以下。
同様に、青い印をつけた数は単調減少列になっているので、青い印のある数はk+1個以下。
そして、数列全体で最大の数は赤と青の両方の印があるので、数列全体で、
k^2+(k+1)+(k+1)-1=(k+1)^2個以下の数しかないことがわかります。
よって、n=kのとき命題が成立すると仮定すると、n=k+1のときも命題が成立します。
以上、(i)、(ii)より、
「異なる実数を並べた数列に含まれる単調増加列または単調減少列が全てｎ個以下の数
からなるとき、実数はｎ2個以下である」
が、任意の自然数ｎについて成り立つことが示されました。
よって、その対偶である
「ｎ2+1個以上の異なる実数を並べた数列は、ｎ+1個以上の数からなる単調増加列または単
調減少列を含む」
も成り立つので、最初の命題
「1からｎ2+1までの自然数を並べた数列は、少なくともｎ+1個の数からなる単調増加列また
は単調減少列を含む」
は示されました。 （証終）
DD++さんからのコメントです。（平成２９年７月３０日付け）
もしかしてこういうことなのかなあ、というのを見つけたので．．．。
私は前後から1回ずつ剥ぎ取っていった帰納法で示したわけですが、前からだけ（あるいは
後ろからだけ）n回剥ぎ取る方針でいくと、鳩ノ巣原理を証明中に登場させようと思えばでき
なくはないようです。
まず、「その数はそれより前にあるどの数より大きい」に属する数の集合を A1 とします。
A1 に属する数が n+1 個以上あれば、それらは単調増加列になるので条件を満たします。
以下では、A1 に属する個数が n 個以下であった場合を考えます。
次に、「その数は A1 に属しておらず、それより前にある A1 に属さないどの数より大きい」
に属する数の集合を A2 とします。
すると、A2 に属するどの数も、自身より前にそれより大きな A1 に属する数があることに
なります。A2 に属する数が n+1 個以上あれば、それらは単調増加列になるので条件を満
たします。
以下では、A2 に属する個数も n 個以下であった場合を考えます。
さらに、「その数は A1、A2 に属しておらず、それより前にある A1、A2 に属さないどの数
より大きい」に属する数の集合を A3 とします。
すると、A3 に属するどの数も、自身より前にそれより大きな A2 に属する数があることに
なります。A3 に属する数が n+1 個以上あれば、それらは単調増加列になるので条件を満
たします。
以下では、A3 に属する個数も n 個以下であった場合を考えます。
以下、An ができるまで繰り返します。
A1 から An まで全て n 個以下の場合を考えているので、いずれかの集合に属した数は多
くとも n^2 個。つまり、少なくとも 1 個はどの集合にも属していない数があります。（※）
この数は、自身より前にそれより大きな An に属する数があり、この An に属する数は自
身より前にそれより大きな A(n-1) に属する数があり、以下繰り返して、A1 までたどり着き
ますが、このとき辿った n+1 個の数は、前から順に見れば単調減少列です。
よって、「1 から n^2+1 までの自然数を並べた数列は、少なくとも n+1 個の数からなる単
調増加列または単調減少列を含む」は示されました。
……という証明中の（※）のところ、わざわざ背理法を使うと、こうなります。
もし、この時点で全ての数がいずれかの集合に属していたと仮定すると、集合は n 個で数
は n^2+1 個あるので、鳩ノ巣原理よりいずれかの集合に n+1 個以上含まれることになり、
全ての集合が n 個以下の数しか含まないことに矛盾。
よって、少なくとも 1 個はどの集合にも属していない数があります。
ただ、直接証明に何の困難もないところでわざわざ間接証明を持ち出して、しかも直接証
明より長くなるので、鳩ノ巣原理を使うと綺麗に証明できる命題であるというよりは、鳩ノ巣
原理の話題のために無理して鳩ノ巣原理を使ってみただけの証明という印象が拭えません
ね。
（コメント） DD++さんに触発されて、何とか例題２０の鳩ノ巣原理的解法をでっち上げてみ
ました。（平成２９年８月４日付け）
（解） １から１０までの自然数を並べた数列を、ａ1、ａ2、・・・、ａ10 とする。（これが、鳩）
ａｋに対して、座標が（ｘｋ，ｙｋ）の格子点を考える。
ただし、ｘｋ は、ａｋで終わる単調減少列の長さの最大値で、同様に、ｙｋ は、ａｋから始まる
単調増加列の長さの最大値とする。
いま、どの自然数に対しても、その座標（ｘｋ，ｙｋ）が、１≦ｘｋ≦３ 、１≦ｙｋ≦３ とする。
（これが、鳩ノ巣）
このとき、鳩ノ巣原理により、同じ座標を持つ２つの自然数 ａｍ、ａｎ （ｍ＜ｎ） が存在する。
すなわち、 ａｍ、ａｎ から定まる座標を、（ｘｍ，ｙｍ）、（ｘｎ，ｙｎ） とすると、
ｘｍ＝ｘｎ かつ ｙｍ＝ｙｎ だが、 ａｍ＜ａｎ なので、これは起こりえない。
すなわち、「３個以下の数からからなる単調増加列および単調減少列を含む」とすると、
鳩ノ巣原理から矛盾が導き出せることがわかった。
よって、少なくとも４個の数からなる単調増加列または単調減少列を含む。 （終）
（コメント） 例えば、
９ 、１ 、２ 、４ 、８ 、５ 、７ 、６ 、３ 、１０
について、
ａ1 ・・・ （ｘ1，ｙ1）＝（１，１）
ａ2 ・・・ （ｘ2，ｙ2）＝（２，４）
ａ3 ・・・ （ｘ3，ｙ3）＝（１，３）
ａ4 ・・・ （ｘ4，ｙ4）＝（１，２）
ａ5 ・・・ （ｘ5，ｙ5）＝（１，１）
ａ6 ・・・ （ｘ6，ｙ6）＝（２，２）
ａ7 ・・・ （ｘ7，ｙ7）＝（１，１）
ａ8 ・・・ （ｘ8，ｙ8）＝（２，１）
ａ9 ・・・ （ｘ9，ｙ9）＝（３，２）
ａ10 ・・・ （ｘ10，ｙ10）＝（１，１）
から、１から始まる長さ４の単調増加列 １ 、２ 、４ 、８ が存在することが分かる。
（追記） 当ＨＰ読者のＨＮ「河童」さんからメールで、例題２０の別証をいただきました。
（令和５年２月１１日付け）
少しでも高校生の役に立ちたいと、塾講師やオンライン家庭教師などを行っております。
例題２０ １から１０までの自然数を並べた数列は、少なくとも４個の数からなる単調増加
列または単調減少列を含むことを示せ。
について、次のような証明はいかがでしょうか。
（証明） 乱数表を使って、１から１０までの１０個の自然数を並べた、
９ 、１ 、２ 、４ 、８ 、５ 、７ 、６ 、３ 、１０
で説明します。例えば、８を末項に持つ数列 ９，１，２，４，８ を考えますと、これは、
｛１，２，４，８｝という増加列を含み、｛９，８｝という減少列を含みます。これを項数でもって
（４，２）と表すことにします。
８の次の５で同様に考えると、｛１，２，４，５｝｛９，８，５｝を含みますから（４，３）と表せます。
８から５に移る際に、５が８より小さいことから、減少列の項がひとつ増えます。
増加列、減少列のいずれかは変化して、他方は変化しないです。
しかし、８から５、７へと移るに従い、増加列、減少列のいずれか一方は必ず変化します。
増加列、減少列ともに項数が３以下のものは、（１，１）、（１，２）……（３，３）の合計９個あ
り、それに対して、元の数列の項数は１０項ですから、増加列または減少列が４以上のもの
が必ず１つは含まれるはずです。 （証終）
（コメント） 河童さん、証明をいただきありがとうございます。内容的には、私の証明と趣旨
は同じかな？と思います。ただ、項が飛んでいる部分、すなわち、
｛１，２，４，８｝という増加列を含み、｛９，８｝という減少列を含みます。
としている点が気にかかります。
DD++ さんからのコメントです。（令和５年２月１４日付け）
河童さんの証明だと、(ｍ，ｎ) という数字の組が「隣接するところでは必ず異なる」ことしか
言っておらず、不完全に思います。
２回変化したり、４回変化して元の数の組に戻る可能性を否定する根拠も必要なのでは。
Dengan kesaktian Indukmu さんからのコメントです。（令和５年２月１５日付け）
鳩ノ巣原理を使うアイデアの初出は以下の論文のようですね。
A. Seidenberg, A Simple Proof of a Theorem of Erdos and Szekeres, Journal of the London
Mathematical Society, Volume s1-34, Issue 3, July 1959, Page 352, https://doi.org/10.1112
/jlms/s1-34.3.352
よおすけさんからのコメントです。（平成２９年７月１９日付け）
が有理数でないことを、鳩ノ巣原理を使って証明できますか。
DD++さんからのコメントです。（平成２９年７月１９日付け）
やろうと思えば出来なくはないですね。無理数の証明で直接証明的になるのは珍しいです
が、果たしてこの方法をやるメリットがあるかといえば、「ない」と思います。さっさと無限降下
法に持ち込んだ方が簡潔ですし．．．。
（証明） m[0]+m[1]=0 を満たす整数 m[0] と m[1] について考えます。
このとき、m[0]^2 = 2*m[1]^2 ≧ m[1]^2 ≧ 0 より、|m[0]| ≧ |m[1]| です。また、
m[0]^2 = 2*m[1]^2 より、m[0]^2 は偶数、よって m[0] は偶数なので、m[2] = m[0]/2 は整数
で、2*m[2]+m[1]=0 から m[1]+m[2]=0
同様に、m[1]^2 = 2*m[2]^2 ≧ m[2]^2 ≧ 0 より、|m[1]| ≧ |m[2]| です。また、
m[1]^2 = 2*m[2]^2 より、m[1]^2 は偶数、よって m[2] は偶数なので、m[3] = m[1]/2 は整数
で、2*m[3]+m[2]=0 から m[2]+m[3]=0
以下、同様に繰り返して、m[|m[0]|]+m[|m[0]|+1]=0 となるところまで繰り返します。
m[0], m[1], m[2], m[3], ……, m[|m[0]|], m[|m[0]|+1] という数列を作ると、これらは絶対値が
単調減少する整数列なので、その絶対値は 0, 1, 2, ……, |m[0]| の |m[0]|+1 通りしかあり得
ず、鳩ノ巣原理よりこれらの |m[0]|+2 個の中に同じ絶対値を取るものが存在し、しかもそれ
らは隣接項です。
それらを m[k] と m[k+1] とすると、|m[k]| = |m[k+1]| かつ m[k]+m[k+1]=0 なので、連立
方程式を解いて、m[k] = m[k+1] = 0
すると、m[k-1] = 2*m[k+1] = 0 などのようにして、この数列は全て 0 であることが示されま
す。
よって、m[0]+m[1]=0 を満たす整数は、m[0] = m[1] = 0 に限られる、つまり 1 と
は有理数体上一次独立なので は無理数です。 （証終）
例題２１ １から１０までの自然数を円形に並べる。このとき、連続して並ぶ３数の和で１７
以上のものが存在する。
都合よく、「３、５、９」などと連続して並んでいれば、和が１７で存在！となるが、上記の問
題の核心は、「１から１０までの自然数がランダムに円形に並んでいる」とき、そのような組
は存在するか、ということである。
この問題を解決するには、「鳩ノ巣原理」が有効である。
（解） 連続して並ぶ３数の組は全部で、１０組（これが鳩ノ巣）あり、その総和は、
（１＋２＋・・・＋１０）×３＝１６５ （これが鳩）
よって、少なくとも１組の和は１７以上である。 （終）
（コメント） 上記では「和が１７以上」であったが、実は、「和が１８以上」とも出来る。
実際に、１以外の２から１０までの９つの自然数の総和は、５４（これが鳩）で、３数ずつ３
組（これが鳩ノ巣）に分けると、和は平均して、５４÷３＝１８ なので、少なくとも１組の和は
１８以上である。
したがって、任意の並びで、連続する３数の和が１８以上となるものが存在する。
ハンニバル・フォーチュンさんからのコメントです。（平成３０年７月１５日付け）
、「少なくとも１組の和は１９以上である。」への反例として、具体的には、
５ １ ９ ７ ２ ６ ８ ４ ３ １０
がありますね！「少なくとも１組の和は１８以上である」が最良の評価のようです。
ハンニバル・フォーチュンさんからのコメントです。（平成３０年８月３０日付け）
OEIS の「A066385」に於いて一般化した話題があります。
"Smallest maximum of sum of 3 consecutive terms in any arrangement of [1..n] in a circle."
だそうです。例題２１は n=10 のときのお話でした。
また、17 ≦ n ≦ 38 のときに、 a(n)=3n + 5 - a(n-1) の関係があるようです。
まことに不思議な感じがいたします。
（追記） 令和３年１１月１７日付け
例題２２ ｎ個の自然数 ａ1、ａ2、・・・、ａｎ がある。このとき、連続する和
ａk＋ａk+1＋・・・＋ａm （ｋからｍまでは連続する自然数）
で、ｎで割り切れるものが必ず存在する。
（解） Ｓ1＝ａ1、Ｓ2＝ａ1＋ａ2、Ｓ3＝ａ1＋ａ2＋ａ3、・・・、Ｓn＝ａ1＋ａ2＋・・・＋ａn とおく。
Ｓ1、Ｓ2、Ｓ3、・・・、Ｓn の中にｎで割り切れるものが少なくとも一つあれば、結論は言える。
よって、Ｓ1、Ｓ2、Ｓ3、・・・、Ｓn の何れもｎで割り切れないものとする。（これが、鳩）
ｎで割った余りは、１、２、・・・、ｎ−１の ｎ−１個ある。（これが、鳩ノ巣）
鳩ノ巣原理により、Ｓ1、Ｓ2、Ｓ3、・・・、Ｓn の中に、ｎで割った余りが同じものが必ず存在
する。
したがって、自然数 ｋ、ｍ（ｋ≦ｍ）に対して、
Ｓｋ-1−Ｓｍ＝ａk＋ａk+1＋・・・＋ａm≡０ （ｍｏｄ ｎ）
となるものが必ず存在する。すなわち、
ａk＋ａk+1＋・・・＋ａm （ｋからｍまでは連続する自然数）
で、ｎで割り切れるものが必ず存在する。 （終）
以下、工事中！