5つの整数から3つ選んで和を3の倍数に

方針

解答

⓪ 発想 — どう考え始めるか。 和が3の倍数かどうかは、各数の3で割った余りだけで決まる。だから5つの数を、余り $0,1,2$ の3つの部屋に分類して考える。

部屋の使われ方は、大きく2通りしかない。3部屋すべてに数があるか。使われる部屋が2つ以下か。

前者なら、余り $0+1+2=3$ の組合せで一撃だ。後者なら、5個を2部屋に入れるのだから、鳩の巣原理で「同じ部屋に3個」が保証される。$r+r+r=3r$ でやはり一撃。どちらに転んでも、3の倍数の和が作れる。

① 余りで分類する。 5つの整数を、3で割った余り($0,1,2$)によって3組に分ける。和の余りは、各数の余りの和で決まる。

② 3種類の余りがすべて現れる場合。 余り $0,1,2$ の数を1つずつ選ぶ。和の余りは

$$0+1+2=3\equiv 0(\mathrm{mod}3)$$

和は3の倍数になる。

③ 現れる余りが2種類以下の場合。 5個の数が、高々2つの組に入っている。鳩の巣原理により、どちらかの組に3個以上入っている。その組から3つ選べば、余りはすべて同じ $r$ で、和の余りは

$$r+r+r=3r\equiv 0(\mathrm{mod}3)$$

やはり3の倍数だ。①②③より、つねに可能である。

まとめ: 「全種類そろう」か「どれかに偏る」か。この二者択一は、どちらに転んでも勝てるようにできている。5という個数は最良で、4つの整数(たとえば $0,0,1,1$)では3つの和を3の倍数にできない。ぎりぎりの線で成り立つ定理だと見えれば完璧だ。

発展 — 一歩先へ。 この事実は一般化できる。「どんな $2n-1$ 個の整数からも、$n$ 個選んで和を $n$ の倍数にできる」(本問は $n=3$、$2\cdot 3-1=5$)。エルデシュ・ギンツブルグ・ジヴの定理と呼ばれ、$2n-2$ 個では反例が作れる。余りで分類する発想は、その入り口に立っている。

別解

部屋割りの全パターン表で押す(苦手な人向け)。 「場合分けが本当に全部なのか不安」という人は、部屋割りの内訳を全部書き出してしまえばよい。

5個を3部屋(余り $0,1,2$)に入れる内訳は、人数の組だけ見れば次の5通りしかない:

• $(5,0,0)$ 型: 同じ部屋に5個。そこから3個選べば $r+r+r\equiv 0$ ✓
• $(4,1,0)$ 型: 4個の部屋から3個 ✓
• $(3,2,0)$ 型: 3個の部屋から3個 ✓
• $(3,1,1)$ 型: 3個の部屋から3個 ✓
• $(2,2,1)$ 型: 3部屋すべてに数がある。1つずつ選んで $0+1+2\equiv 0$ ✓

どの行でも、「同じ部屋3個」か「3部屋から1個ずつ」のどちらかが必ず取れる。5行の表がそのまま証明になる。

本解の「3種類そろう or 偏る」という二分は、この表を2グループにまとめた言い方だ。表で確かめてから二分の言葉に戻ると、論理の骨組みがはっきり見える。