インテジャーズ

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
セメレディの定理の組合せ論的証明ー6 - INTEGERS
セメレディの定理の組合せ論的証明ー7 - 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の最後の方や セメレディの定理の組合せ論的証明ー4 - INTEGERS で利用している)。

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

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

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