鳩の巣原理。

PIGEONHOLE PRINCIPLE — ツギノテ。FUN 編集部

鳩の巣原理とは、巣が10個しかないところに鳩が11羽入れば、どこかの巣には2羽以上いる、という言い切りのことです。当たり前に聞こえますが、当たり前なのが取り柄です。どの巣にいるかを一羽ずつ確かめなくても、「2羽入っている巣が必ずある」とだけは言えてしまいます。

言い方を整えると、こうなります。n個の入れ物にn+1個以上のものを入れると、少なくとも1つの入れ物には2個以上が入る。入れ物を引き出しに見立てて抽斗原理、あるいは19世紀の数学者ディリクレの名からディリクレの箱入れ原理とも呼ばれます。

数えないで言い切るための道具

この原理の使いどころは、「どこに」ではなく「あるかないか」だけを問われている場面です。中身の配り方は無数にありますが、どう配っても逃げ場がない。だから場合分けを全部並べずに結論が出ます。組み合わせ論の教科書で、最初のほうに出てくる理由がこれです。

一般形もあります。n個の入れ物にm個のものを入れるなら、どれかの入れ物には m÷n 以上（端数は切り上げ）が入っている。25個のものを4つの箱に配れば、どこかの箱には必ず7個以上ある、という具合です。

色柄の違う靴下が10種類、それぞれ2枚ずつ、合わせて20枚が引き出しで混ざっているとします。見ないで引いて、同じ種類が2枚そろうまでに最悪何枚引くことになるか。答えは11枚です。種類が10しかないので、11枚あれば必ずどこかが重なる。

逆に10枚で止まると、「10種類から1枚ずつ」という配り方があり得るので、そろわない可能性が残ります。この原理は最悪の場合だけを保証するので、平均が知りたいときには使えません。そこは別に数える必要があります。

補足：英語の pigeonhole は伝書鳩の巣箱と、書類を仕分ける仕切り棚の両方を指す。ディリクレは1834年に Schubfachprinzip（引き出しの原理）という語で用いており、鳩の比喩が定着した経緯については諸説あり、本紙では初出を確認できていない。