51個の数から割り切る対がある(鳩の巣原理)

方針

解答

⓪ 発想 — どう考え始めるか。 「必ず存在する」の証明は鳩の巣原理(引き出し論法)が定番: 箱の数より多くを選べば、同じ箱に2つ入る。

急所は箱の設計だ。各整数を $2^k\times (\text{奇数})$ の形に一意に書き、「奇数部分」で分類する。$1$ から $100$ の奇数は $1,3,\dots ,99$ の50個 — 箱は50個。

$51$ 個選べば同じ箱の2数がある。同じ箱の2数は $2^{i}d$ と $2^{j}d$($i<j$)の形で、前者が後者を割り切る。

① 奇数部分で分類。 $1$ から $100$ の各整数を $2^k\times m$($m$ は奇数)と一意に表す。奇数部分 $m$ は $1,3,5,\dots ,99$ の $50$ 通り。これを箱とする。

② 鳩の巣。 $51$ 個の数を、その奇数部分($50$ 通り)で分けると、$51>50$ より、同じ奇数部分 $m$ をもつ $2$ 数 $a=2^{i}m,b=2^{j}m$($i<j$)が必ずある。

③ 割り切る。 $a=2^{i}m,b=2^{j}m$($i<j$)なら $\frac{b}{a}=2^{j-i}$ は整数だから、$a$ は $b$ を割り切る。よって割り切る対が存在する。

まとめ 整数を $2^k\times$奇数と書き、奇数部分($50$ 通り)を箱に。$51$ 個なら鳩の巣で同じ奇数部分の $2$ 数があり、一方が他方を割り切る。命題(鳩の巣)と整数の融合。

発展 — 一歩先へ。 「割り切る」という関係で並べた鎖と、その反対の「どの2つも割り切らない」集まり(反鎖)の攻防は、順序集合の理論(ディルワースの定理)の入り口だ。本問は「最長の反鎖が50個($51\sim 100$)」「鎖が50本で全体を覆える」という2つの50がぴったり一致する実例で、この一致は偶然ではない — という美しい一般定理につながっている。

別解

「鎖」で見る+50個ではダメなことの実例(問題の鋭さ)。 各箱の中身を書き出すと、奇数 $d$ の箱は

$$\{d,2d,4d,8d,\dots \}\cap \{1,\dots ,100\}$$

倍々の鎖であり、鎖の中のどの2数も「一方が他方を割り切る」関係にある。つまり本問は「50本の鎖に51個を配れば、どこかの鎖に2個入る」という構図だ。

さらに、51という数が最良であることも確かめられる。$51,52,\dots ,100$ の50個を選ぶと、どの2数も比が2未満なので割り切る対が存在しない(倍以上でないと割り切れない)。50個なら回避できて、51個なら不可能 — 鳩の巣の評価がぴったり鋭いことまで含めて、この問題の全景になる。