この用語はまだ監査を通っていません（未確認）。
鳩の巣原理
はとのすげんり ／ 部屋割り論法 ／ ディリクレの箱入れ原理 1対1で対応pigeonhole principle
名詞 ・書き言葉・答案
式と読み方
the ceiling of n over k
定義
n 個の箱に n より多くの物を入れると、2 個以上入る箱が少なくとも 1 つあるという原理。一般に n 個の物を k 個の箱に入れると、⌈n/k⌉ 個以上入る箱がある。
The principle that if more than n objects are put into n boxes, some box gets at least two of them. More generally, if n objects go into k boxes, some box holds at least ⌈n/k⌉ objects.
例文
話し言葉 There are 13 people in this room, so by the pigeonhole principle, at least two of them were born in the same month. この部屋には 13 人いるので、鳩の巣原理から、少なくとも 2 人は同じ月に生まれている。
書き言葉・答案 Use the pigeonhole principle to show that among any 5 integers, there are two that leave the same remainder when divided by 4. 鳩の巣原理を用いて、任意の 5 つの整数の中に、4 で割った余りが等しいものが 2 つあることを示せ。
言い間違えやすいところ
- pigeonhole は「鳩の巣」ではなく、鳩小屋の仕切りや書類の仕分け棚を指す語。英語では pigeon nest とは言わず、pigeonhole principle で 1 つの名前。
- 日本の入試問題の解説では「部屋割り論法」と呼ぶことがある。証明の中では by the pigeonhole principle と理由を添える。
- 用例コーパスでは話し言葉には出てこず、書き言葉はすべて MIT の講義ノート。Levin の本では 5 件（1.4 Proofs ほか）。