第2問

a_1, a_2, \dots

を、正の項と負の項をそれぞれ無限に含む整数列とする。任意の正の整数

n

に対して、

a_1, a_2, \dots, a_n

を

n

で割った余りが

n

通りとも互いに異なるとする。このとき、すべての整数がこの数列にちょうど一回ずつ現れることを証明せよ。

ステップ 1/5: どの項も重複しない

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

ざっくり言うと

もし二つの項が等しければ、それらは自明に同じ余りを持ち、初めの余りがすべて異なるという仮定に反する。

i<j,\ a_i=a_j\ \Longrightarrow\ \text{contradiction at }n=j

詳しい解説

ある $i<j$ に対し $a_i=a_j$ と仮定し、 $n=j$ とする。 $a_1,\dots,a_n$ の中では仮定により $n$ で割った余りが $n$ 通り相異なるはずだが、 $a_i=a_j$ なので自明に $a_i\equiv a_j\pmod n$ となり矛盾する。よって各整数は数列中に高々一回しか現れない。