13 人いれば誕生月が必ず重なる？鳩の巣原理で示す

13 人集まれば、同じ月に生まれた人が必ず 2 人以上います。誰の誕生日も調べる必要はありません。

月は 12 種類しかないので、13 人を割り振れば必ずどこかが重なる。これが鳩の巣原理です^[1]。

いくつあるかではなく、必ずあるかを示す

これまでの問題は「何通りあるか」を数えるものでした。鳩の巣原理が答えるのは「必ず存在するか」です。

数えるのではなく、入れ物の数と入れるものの数を比べる。それだけで結論が出ます。

$n$ 個のものを $m$ 個の入れ物に入れ、$n>m$ ならば、2 個以上入る入れ物が必ずある^[2]。

何個以上入るかまで言える

もっと強い形もあります。$n$ 個を $m$ 個の入れ物に入れると、少なくとも $\lceil \frac{n}{m}\rceil$ 個入る入れ物がある^[3]。

記号は切り上げです。$25$ 人を 12 か月に割り振るなら $\lceil \frac{25}{12}\rceil =3$ で、同じ月生まれが 3 人以上いる月が必ずあります。

すべての入れ物が $\lceil \frac{n}{m}\rceil -1$ 個以下だとすると、合計が $n$ に届かない。だから矛盾します。

入れ物の作り方がすべて

原理そのものは単純です。難しいのは、何を入れ物にするかを見つけるところ。

誕生月なら 12 個の月が入れ物です。ここまでは自然に思いつく。実際の問題では、入れ物を自分で設計します。

例：和が 11 になる組

$1$ から $10$ までの数から 6 個を選ぶと、和が 11 になる 2 数が必ず含まれます。

入れ物を、和が 11 になるペアで作ります。$\{1,10\}$、$\{2,9\}$、$\{3,8\}$、$\{4,7\}$、$\{5,6\}$ の 5 組。

6 個の数を 5 個の組に割り振るので、どこかの組から 2 個選ばれます。その 2 数の和が 11 です。

5 個までなら、各組から 1 個ずつ選んで条件を避けられます。6 個が境目です。

例：差が割り切れる 2 数

整数を $n+1$ 個選ぶと、差が $n$ で割り切れる 2 数が必ずあります。

入れ物は、$n$ で割った余りです。余りは $0$ から $n-1$ までの $n$ 通りしかない。

$n+1$ 個の整数を $n$ 個の余りに割り振れば、同じ余りの 2 数が出ます。その差は $n$ の倍数です。

2 桁の整数を 12 個選べば、差が 11 で割り切れる 2 数がある。余りが 11 通りしかないためです^[2]。

例：一方が他方を割り切る

$1$ から $100$ までから 51 個を選ぶと、一方が他方を割り切る 2 数が必ずあります。

どの整数も、2 のべき乗と奇数の積に一通りに書けます。$12=2^2\times 3$、$40=2^3\times 5$ のように。

入れ物を、この奇数の部分で作ります。$1$ から $99$ までの奇数は 50 個しかない。

51 個を 50 個の入れ物に割り振れば、奇数部分が同じ 2 数が出ます。その 2 数は 2 のべき乗だけが違うので、小さいほうが大きいほうを割り切ります。

例：中点が格子点になる 2 点

座標が整数の点を 5 個選ぶと、中点も整数の座標になる 2 点が必ずあります。

入れ物を、$x$ 座標と $y$ 座標の偶奇で作ります。偶と偶、偶と奇、奇と偶、奇と奇の 4 通り。

5 点を 4 通りに割り振れば、偶奇の型が同じ 2 点が出ます。その 2 点の座標を足すとどちらも偶数になるので、中点の座標は整数です。

例：握手の回数

$n$ 人が集まって握手をします。握手した回数が同じ人が必ず 2 人います^[1]。

1 人あたりの回数は $0$ から $n-1$ までの $n$ 通り。人数も $n$ なので、そのままでは入れ物が足りています。

ただし、$0$ 回の人と $n-1$ 回の人は同時にいられません。全員と握手した人がいるなら、0 回の人はいないからです。

だから実際に使われる入れ物は $n-1$ 通り以下。$n$ 人を割り振れば必ず重なります。

例：靴下を取り出す

引き出しに黒と青の靴下が混ざっています。暗闇で 3 枚とり出せば、同じ色の 2 枚が必ず含まれます^[1]。

色は 2 種類なので、3 枚を割り振ればどこかが 2 枚になる。何枚ずつ入っているかは関係ありません。

3 色なら 4 枚、$k$ 色なら $k+1$ 枚です。

逆は言えない

鳩の巣原理が言うのは「必ずある」だけです。いくつあるかも、どこにあるかも分かりません。

13 人いれば同じ月の 2 人がいる、とは言えます。しかし何月かは分からないし、3 人以上いるかも分からない。

存在を示す原理であって、数える原理ではない。ここをとり違えないようにします。

境目を確かめる

原理を使ったら、1 つ少ないと成り立たないことも確かめます。

$1$ から $10$ から 5 個なら、$1,2,3,4,5$ を選べば和が 11 になる組はありません。6 個が本当の境目だと分かります。

12 人なら、各月に 1 人ずつという配置ができる。13 人が境目です。

境目を示せて、はじめて答えが完成します。

よくある誤り

数えるのではなく、比べる。入れ物さえ思いつけば、あとは 1 行で終わります。

参考文献

^[1] が原理の基本形と古典的な例、^[2] と ^[3] が各国語での定式化と応用、^[4] が場合分けして足す規則、^[5] が組合せの公式です。