第4問

\mathbb{Z}

をすべての整数からなる集合とする。次の性質を満たす整数係数多項式

P(x)

をすべて求めよ：

\mathbb{Z}

の各整数がちょうど1回ずつ現れる整数の無限数列

a_1,a_2,\ldots

に対して、常に添字

i<j

と整数

k

が存在して

a_i+a_{i+1}+\cdots+a_j=P(k)

となる。

ステップ 2/5: 1次の P は成立する：d と mod c で合同な区間和を見つける

前のステップ次のステップ

s_i\equiv s_j \pmod c,\ i<j \implies a_{i+1}+\cdots+a_j\equiv 0\pmod c

詳しい解説

$P(x)=cx+d$ 、 $c\ne0$ とし、 $s_0=0$ 、 $s_i=a_1+\cdots+a_i$ とおく。区間和 $a_i+\cdots+a_j=s_j-s_{i-1}$ がある整数 $k$ に対し $P(k)=ck+d$ となるのは、ちょうど $s_j-s_{i-1}\equiv d\pmod c$ のときである。各整数がちょうど1回現れるので、 $a_e\equiv d\pmod{|c|}$ を満たす位置 $e$ は無限に存在する；そのうち $|c|+1$ 個 $e_1<\cdots<e_{|c|+1}$ を選ぶ。 $a_{e_l}\equiv d\pmod c$ なので $s_{e_l}\bmod c$ は $s_{e_l-1}\bmod c$ によって定まり、これは $|c|$ 通りの値しか取らない；鳩の巣原理により、ある $p<q$ で $s_{e_p-1}\equiv s_{e_q-1}\pmod c$ となる。