1 から 10 で 6 個選ぶと必ず割り切れる組ができる、部屋割り論法という道具

$1$ から $10$ の中から 6 個どう選んでも、一方が他方を割り切る 2 数が必ず含まれます。$\{4,6,7,9,10,5\}$ なら $5$ と $10$。

選び方は 210 通りありますが、1 つずつ確かめる必要はありません。箱を 5 つ用意して、6 個を入れるだけで済みます。

原理そのもの

$n$ 個のものを $m$ 個の箱に入れ、$n>m$ なら、2 個以上入る箱が必ずあります^[1]。

当たり前に見える主張です。使いにくさは別のところにあり、何を箱にするかを自分で決めなければなりません^[2]。

箱の個数が「調べたい条件の種類の数」になるように選ぶ。ここが唯一の工夫どころです。

$11$ 個までは、余りをすべて別にして入れられます。$12$ 個目で必ずぶつかる。

例：差が 11 の倍数になる 2 数

2 桁の数を 12 個選ぶと、差が $11$ の倍数になる 2 数が必ずあります^[2]。

$11$ で割った余りは $0$ から $10$ の 11 通り。これを箱にします。12 個を 11 個の箱に入れるので、同じ箱に 2 個入る。

同じ余りの 2 数は、差が $11$ で割り切れます。2 桁の数の差なので、$11$、$22$、$33$ のようにゾロ目になる。

例：同じ余りの 2 数を作る

一般化すると、$m$ 個の箱の話になります。整数を $m+1$ 個選べば、$m$ で割った余りが等しい 2 数が必ずある。

余りは $0$ から $m-1$ の $m$ 通りしかないためです。差が $m$ の倍数になる 2 数が手に入ります。

$m=100$ なら、$101$ 個の整数から下 2 桁が一致する 2 数を選び出せる。数の大きさは関係ありません。

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

$1$ から $2n$ の中から $n+1$ 個選ぶと、一方が他方を割り切る 2 数が必ずあります。$n=5$ なら冒頭の主張です。

箱に使うのは、各数から $2$ をすべて割り出したあとに残る奇数の部分。$12=2^2\times 3$ なら $3$、$8=2^3$ なら $1$ です。

$1$ から $2n$ の中の奇数は $1,3,5,\dots ,2n-1$ の $n$ 個。箱は $n$ 個しかありません。

同じ箱に入った 2 数は、奇数の部分が同じで $2$ のべきだけが違います。$4=2^2\times 1$ と $8=2^3\times 1$ なら、$4$ が $8$ を割り切る。

$n+1$ 個を $n$ 個の箱に入れるので、同じ箱の 2 数が必ず現れる。これで示せました。

例：連続する何個かの和

整数を $n$ 個並べたとき、連続する何個かの和が $n$ の倍数になるものが必ずあります。

箱にするのは部分和の余り。$S_0=0$、$S_1=a_1$、$S_2=a_1+a_2$ と作ると、$S_0$ から $S_n$ まで $n+1$ 個できます。

余りは $n$ 通りなので、等しくなる 2 つがある。$S_i\equiv S_j$ なら差の $S_j-S_i$ が $n$ の倍数で、これが連続する和です。

$S_1=3$ と $S_3=8$ が、どちらも $5$ で割ると余り $3$。差の $8-3=5$ が、$2$ 番目と $3$ 番目の和にあたります。

例：3 個選んで和を 3 の倍数にする

整数を 5 個どう並べても、その中の 3 個で和が $3$ の倍数になるものがあります。

箱は $3$ で割った余りの $0$、$1$、$2$ の 3 つ。どれかの箱に 3 個以上入っていれば、その 3 個を選べば和が $3$ の倍数です。

そうでなければ、どの箱も 2 個以下。$2+2=4<5$ なので、少なくとも 3 つの箱に 1 個ずつ入っています。

各箱から 1 個ずつとれば、余りの和は $0+1+2=3$ で $3$ の倍数。どちらに転んでも見つかりました。

例：整数に近い倍数を作る

無理数 $x$ に対し、$\{x\}$ を小数部分とします。$0$、$\{x\}$、$\{2x\}$、$\dots$、$\{nx\}$ の $n+1$ 個を並べる。

区間 $[0,1)$ を $n$ 等分すると箱が $n$ 個。$n+1$ 個を入れるので、同じ箱に 2 つ入ります^[3]。

その 2 つの差をとると、ある整数倍が整数にきわめて近いと分かる。有理数による近似の精度が、これで押さえられます。

箱の選び方

うまくいく箱は、たいてい「余り」か「型で分けたもの」です。

奇数部分で分けたのも、部分和の余りで分けたのも、同じ形です。有限通りに落とす一手が見つかれば、あとは数を比べるだけ。

答えを確かめる

主張がぎりぎりかどうかを、境目で確かめます。$1$ から $10$ なら、$6$ から $10$ の 5 個には割り切れる組がありません。

$6$ 個にすると必ず現れる。$n$ 個では作れて $n+1$ 個では作れない、という形になっていれば、条件が最良だと分かります。

箱の個数を数え違えていないかも見ます。$11$ で割った余りは $0$ から $10$ の 11 通りで、$10$ 通りではありません。

まちがえやすい点

有限通りに落とす分け方を 1 つ見つける。難しいのはそこだけで、見つかったあとの議論は 2 行で終わります。

出典