INTEGERS

数、特に整数に関する記事。

鳩ノ巣原理

その他

鳩ノ巣原理(pigeonhole principle)、鳩の巣原理、Dirichletの(箱入れ)原理(box principle)、Dirichletの抽斗論法、部屋割り論法などと呼ばれる次の原理*1は有名です。

鳩ノ巣原理 $n$ を正整数とする。 $n+1$ 羽以上の鳩を $n$ 個の鳩ノ巣に入れるとき、少なくとも一つの鳩ノ巣に二羽の鳩が入る。

当ブログで鳩ノ巣原理を利用している記事に

ディリクレの近似定理 - INTEGERS
ファン・デル・ヴェルデンの定理 - INTEGERS
ベイカーの定理の証明 - INTEGERS

などがあります。次のように拡張したものはしばしば一般化鳩ノ巣原理と呼ばれます。

一般化鳩ノ巣原理 $n, k$ を正整数とする。 $kn+1$ 羽以上の鳩を $n$ 個の鳩ノ巣に入れるとき、少なくとも一つの鳩ノ巣に $k+1$ 羽の鳩が入る。

$k=1$ のときを考えると鳩ノ巣原理となるため、一般化鳩ノ巣原理は確かに鳩ノ巣原理の一般化です。これは次のように表現することもできます。

一般化鳩ノ巣原理(言い換え) $n, k$ を正整数とする。このとき、非負整数 $a_1, \dots, a_n$ に対して

$\displaystyle \sum_{i=1}^na_i \geq kn+1$

ならば、或る $j$ が存在して $a_j \geq k+1$ が成り立つ。

これは $1, \dots, n$ が鳩ノ巣の番号で、 $i$ 番の鳩ノ巣に入っている鳩の羽数を $a_j$ として記述したものです。

さて、この記事の本論は簡単に証明できる次の命題についてです。

命題 $n$ を正整数、 $t$ を正の数とする。このとき、実数 $a_1, \dots, a_n$ に対して

$\displaystyle \sum_{i=1}^na_i \geq nt$

ならば、或る $j$ が存在して $a_j \geq t$ が成り立つ。

証明. もし、全ての $i$ に対して $a_i < t$ ならば

$\displaystyle \sum_{i=1}^na_i < nt$

となって矛盾する。 Q.E.D.

この命題(やその変種*2 )を利用するときに「鳩ノ巣原理より」という枕詞が使われることがよくあります*3。

当ブログでは

IMO2006 Problem 6 - INTEGERS
グリーン・タオ論文の§9を読む（その一） - INTEGERS
セメレディの定理の組合せ論的証明ー６ - INTEGERS
セメレディの定理の組合せ論的証明ー７ - INTEGERS
105に関するErdősの予想や剱岳など - INTEGERS

などでこの用法を使っています*4。この用法はあまり見かけない、或いは不自然だと感じる人もいると思いますが、ここでは上記命題から鳩ノ巣原理が出る、すなわち鳩ノ巣原理と全くの無関係なものではない*5ということを指摘しておきます。

命題 $\Longrightarrow$ 一般化鳩ノ巣原理の証明. 命題において $a_1, \dots, a_n$ を非負整数と限定し、 $t=k+\frac{1}{n}$ とする。すると

$\displaystyle \sum_{i=1}^na_i \geq n(k+\frac{1}{n}) =kn+1$

であれば、或る $j$ が存在して $a_j \geq k+\frac{1}{n}$ が成り立つ。しかしながら、 $a_j$ は整数なので $a_j \geq k+1$ でなければならない。 Q.E.D.

もちろん、ただの背理法の応用の一つなので名前なんて付ける必要はないという指摘はもっともです。

*1:原理とは言っても、自然数論の立場でちゃんと証明できます。

*2:不等号が等号なしだったり逆だったり、積で考えたり。或いはもっと一般的に「全体で何かの性質を満たすとき、有限個の類に類別すると少なくとも一つの類でその性質が満たされる」とする論法(ファン・デル・ヴェルデンの定理 - INTEGERSの最後の方やセメレディの定理の組合せ論的証明ー４ - INTEGERS で利用している)。

*3:背理法ですぐ証明できるけれども、論法はいつも同じなのでこの枕詞でわかってもらうという慣習。

*4:偉い人が使っているから使い方が正しいということはないですが、Szemerédiの定理の記事はTaoの原稿をもとに書いたものであり、Taoはよくこの用法でpigeonhole principleという言葉を使っています。

*5:この命題の論法+整数性=鳩ノ巣原理。より大元となる命題のことも鳩ノ巣原理と呼んでしまおうという慣習もあるということ。