問題106：APMO 2020 P4

#106

整数

★★★☆☆

APMO 2020 P4

以下の条件をみたすような整数係数多項式 $P (x)$ をすべて求めよ.

すべての整数がちょうど $1$ 回ずつ現れるような任意の数列 $a_{1}, a_{2}, a_{3}, \dots$ に対し, ある $i < j$ と整数 $k$ が存在し, $a_{i} + a_{i + 1} + \dots + a_{j} = P (k)$ が成り立つ.

解いてみた

兒玉：まずは $P (x)$ の予想を立てましょう
渡辺： $m o d$ で意地悪とかするのかな
平山：とりあえず定数はダメです
渡辺： $P (x) = x + c$
平山：どうせ一次は全部行けそうみたいな
渡辺： $a_{1} + \dots + a_{i} = S_{i}$ とします
平石：いや $P (x) = 2 x$ で偶奇交互にしたらダメやろ
平石：いやそんなことはないですね
渡辺：特定の $m o d$ を避ける構成は無理なのかな
渡辺： $P (x) = c x$ はok
平山：鳩の巣的にokじゃないですかこれ
平石：ほんまか？
渡辺：関係ないけど $P (x)$ 偶数次なら大小評価で潰せそう
平山：偶数次か関係なくない？2次以上ならスカスカで死にそう
渡辺：それはそう、些細な気付きとして
平山： $a$ の奇数番目を適切にデカくすれば
平山：次の偶数番目を未使用の最小にしても大丈夫な気が
渡辺：最小のやつはとれません
宿田：整数。
平山：は？じゃあ絶対値最小ってことで…
平山：鳩ノ巣の説明をちゃんとします、 $P (x) = c x + d$ として $m o d c$ で $d$ になる $a_{i_{1}}, a_{i_{2}}, \dots$ をとります
平山：このとき $(S_{i_{m} - 1}, S_{i_{m}})$ と $(S_{i_{n} - 1}, S_{i_{n}})$ が $m o d c$ で一致するように取れて
平山： $(i, j) = (i_{m} - 1, i_{n})$ とすればOKです
平石：理解です
平山：なにこれ？ギャグ？

解説・感想

工事中

解答

条件をみたすような $P (x)$ は $1$ 次式すべてであることを示す. 以下, 正整数 $i$ に対して, $S_{i} = a_{1} + a_{2} + \dots + a_{i}$ とする.

$P (x) = c x + d$ のとき ( $c \neq 0$ ), $a_{i} \equiv d (\mod c)$ となるような $i$ を小さい順に $i_{1}, i_{2}, \dots$ とする. $k$ を正整数として $S_{i_{k}}$ を $| c |$ で割った余りは高々 $| c |$ 通りだから, 鳩ノ巣原理より, ある正整数 $m < n$ が存在して $S_{i_{m}} \equiv S_{i_{n}} (\mod c)$ が成り立つ. このとき, $a_{i_{m}} + a_{i_{m} + 1} + \dots + a_{i_{n}} = a_{i_{m}} + S_{i_{n}} - S_{i_{m}} \equiv d (\mod c)$ だから, 条件は満たされる.

$P (x)$ が $2$ 次以上,　あるいは定数のときに条件をみたさないことを示す.

$A = {P (n) ∣ n \in Z}$ について次を示す.

補題.

任意の正整数 $M, k$ について, ある整数 $m$ が存在し, $| m | > M$ かつ $m - k, m - k + 1, \dots, m + k - 1, m + k$ のいずれも $A$ の要素でない.

証明.

$P (x)$ が定数, あるいは次数が偶数のときは $A$ は上に有界であるか, または下に有界であるから明らかに成り立つ. 以下, $P (x)$ の次数が $3$ 以上の奇数であるときに考える. 対称性より $P (x)$ の最高次の係数が正であるとしてよい. $P (x + 1) - P (x)$ は最高次の係数が正である次数が偶数の多項式であるから, ある $N > 0$ があり, $| n | ≧ N$ ならば $P (x + 1) - P (x) > 0$ となる. $P (- N), P (- N + 1), P (- N + 2), \dots, P (N)$ の最大値を $K$ とし, $P (n) > K$ をみたすような $N$ 以上の整数 $n$ のひとつを $L$ とする. $A \cap {n ∣ n > K} = {P (L), P (L + 1), P (L + 2), \dots}$ となる. $P (x + 1) - P (x)$ が最高次の係数が正である定数でない多項式であるから, $P (s + 1) - P (s) > 2 k + 1$ かつ $P (s) > M$ をみたすような $L$ 以上の整数 $s$ が存在し, $m = P (s) + k + 1$ が条件をみたす.

ここで, 以下のように $a_{1}, a_{2}, \dots,$ を帰納的に定める.

$a_{1}, a_{2}, \dots, a_{2 i - 2}$ が定まっているとする. $k = | a_{1} | + | a_{2} | + \dots + | a_{2 i - 2} | + i$ として, $m - k, m - k + 1, \dots, m + k$ のいずれも $A$ の要素でないような $m$ は先の補題より無限個存在するから, そのうち $a_{1}, a_{2}, \dots, a_{2 i - 2}$ のいずれとも異なるもののうち絶対値が最小のもの( $2$ つある場合は正のもの)を $a_{2 i - 1}$ とする. さらに, $a_{1}, a_{2}, \dots, a_{2 i - 1}$ でない整数のうち絶対値が最小のもの ( $2$ つある場合は正のもの)を $a_{2 i}$ とする.

数列の定め方より, ${a_{n}}$ にはすべての整数がちょうど $1$ 回ずつ現れる. また, 任意の正整数 $i$ について $| a_{2 i} | ≦ i$ である. ( $| a_{2 i} | > i$ とすると $- i, - i + 1, \dots, i$ のすべてが $a_{1}, a_{2}, \dots, a_{2 i - 1}$ に現れることになり矛盾する.) そして, $S = a_{i} + a_{i + 1} + \dots + a_{2 j - 1}$ , または $S = a_{i} + a_{i + 1} + \dots + a_{2 j - 1} + a_{2 j}$ について, $| S - a_{2 j - 1} | ≦ | a_{i} | + | a_{i + 1} | + \dots + | a_{2 j - 2} | + | a_{2 j} | ≦ | a_{1} | + | a_{2} | + \dots + | a_{2 j - 2} | + j$ より, ${a_{n}}$ の定め方から $S$ は $A$ の要素でない.　以上より $P (x)$ が $1$ 次式でない場合は条件をみたさない.

コメント. 補題の証明を長々としてしまったがグラフを書いたら感覚的にはすぐ分かる話ではある.