連続する和が n の倍数(鳩の巣原理)

方針

解答

⓪ 発想 — どう考え始めるか。 連続和 $a_{i+1}+\cdots +a_j$ は、部分和の差 $S_j-S_i$ で書ける($S_k=a_1+\cdots +a_k$、$S_0=0$)。

だから「連続和が $n$ の倍数」は「$S_i\equiv S_j(\mathrm{mod}n)$ となる $2$ つがある」と同じことだ。

部分和は $S_0,S_1,\dots ,S_n$ の $n+1$ 個。$n$ で割った余りは $n$ 種類しかない。$n+1$ 個を $n$ 個の箱に入れるのだから、鳩の巣原理で同じ箱に入る $2$ つが必ずある。

① 部分和を作る。 $S_0=0,S_k=a_1+a_2+\cdots +a_k$($k=1,\dots ,n$)とすると、これは $n+1$ 個。連続和は差で $$a_{i+1}+a_{i+2}+\cdots +a_j=S_j-S_i.$$ ② 余りで分類。 $S_0,\dots ,S_n$ を $n$ で割った余りは $0,1,\dots ,n-1$ の $n$ 種類。$n+1$ 個の部分和を $n$ 個の余りに分けると、鳩の巣原理で同じ余りをもつ $2$ つ $S_i,S_j$($i<j$)が存在する。

③ 差が $n$ の倍数。 $S_i\equiv S_j(\mathrm{mod}n)$ だから $S_j-S_i$ は $n$ の倍数。すなわち $$a_{i+1}+a_{i+2}+\cdots +a_j=S_j-S_i$$ が $n$ の倍数。これで存在が示せた。

まとめ 連続和を部分和の差とみて、$n+1$ 個の部分和を余り($n$ 種類)で分類。鳩の巣原理で同じ余りの $2$ つがあり、その差の連続和が $n$ の倍数。整数(合同)と鳩の巣原理の融合。

発展 — 一歩先へ。 「連続」を外して「自由に選ぶ」と、話は急に深くなる。任意の $2n-1$ 個の整数からは、和が $n$ の倍数になる $n$ 個を必ず選べる(エルデシュ・ギンツブルク・ジヴの定理)。しかも $2n-2$ 個では足りない($0$ を $n-1$ 個と $1$ を $n-1$ 個の例)。鳩の巣のずっと先にある世界だ。

別解

別解 — 小さな例で鳩の巣を“見る”(苦手な人向け)。 $n=5$、数を $3,7,2,8,4$ としてみる。部分和は

$$S_0=0,S_1=3,S_2=10,S_3=12,S_4=20,S_5=24.$$

$5$ で割った余りは順に $0,3,0,2,0,4$。$6$ 個の部分和に余りは $5$ 種類しかないから、必ずどこかがかぶる。ここでは $S_0$ と $S_2$(どちらも余り $0$)。

差をとると $S_2-S_0=a_1+a_2=3+7=10$。たしかに $5$ の倍数の連続和が見つかった。

$S_0=0$ を仲間に入れておくのがポイントだ。$S_0$ とかぶった場合は「先頭からの連続和」が答えになる。証明の一行一行が、この小さな実験の一般化になっている。