MathLabs

第2問

a1,a2,…a_1, a_2, \dots を、正の項と負の項をそれぞれ無限に含む整数列とする。任意の正の整数 nn に対して、a1,a2,…,ana_1, a_2, \dots, a_n を nn で割った余りが nn 通りとも互いに異なるとする。このとき、すべての整数がこの数列にちょうど一回ずつ現れることを証明せよ。
ステップ 3/5: 最初の nn 項は nn 個の連続整数である
前のステップ次のステップ
ざっくり言うと

帰納法：連続整数のブロックは、その両端のどちらか一方にちょうど一つの整数を加えることでしか拡張できない。

{a1,…,an}={k+1,…,k+n} for some integer k\{a_1,\dots,a_n\}=\{k+1,\dots,k+n\}\ \text{for some integer }k
詳しい解説

nn に関する帰納法（n=1n=1 の場合は自明）。{a1,…,an}={k+1,…,k+n}\{a_1,\dots,a_n\}=\{k+1,\dots,k+n\} ならば、このブロックと kk を合わせて n+1n+1 個の連続整数 k,k+1,…,k+nk,k+1,\dots,k+n となり、これは mod n+1n+1 の各余りをちょうど一回ずつ実現する。ブロック {a1,…,an}\{a_1,\dots,a_n\} はちょうど kk の余りだけを欠いている。a1,…,an+1a_1,\dots,a_{n+1} も mod n+1n+1 の n+1n+1 通りの余りをすべて実現しなければならないので、an+1≡k(modn+1)a_{n+1}\equiv k\pmod{n+1} が必要である。前のステップより ∣an+1−a1∣<n+1|a_{n+1}-a_1|<n+1 かつ a1∈{k+1,…,k+n}a_1\in\{k+1,\dots,k+n\} なので、a1a_1 に近く kk と mod n+1n+1 で合同な整数は kk と k+n+1k+n+1 しかない。どちらを選んでも、ブロックはちょうど一つの連続整数だけ拡張される。