第3問

正の整数からなる無限数列

a_1,a_2,a_3,\ldots

と正の整数

N

を考える。各

n>N

に対して、

a_n

はリスト

(a_1,a_2,\ldots,a_{n-1})

の中に

a_{n-1}

が現れる回数に等しいとする。数列

a_1,a_3,a_5,\ldots

と

a_2,a_4,a_6,\ldots

の少なくとも一方は、ある時点から周期的になることを証明せよ。

ステップ 1/6: 塔のイメージ

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

ざっくり言うと

数列の各項に番号付きのブロックを一つ用意し、その値を名前とする塔に入れると想像する。すると、添字 N より後の各新しい項は、直前の項が指し示す塔の現在の高さにちょうど等しい。

M=\max(a_1,\ldots,a_N)

詳しい解説

$M=\max(a_1,\ldots,a_N)$ とおき、 $1,2,3,\ldots$ と番号を振った塔の列を考える。 $i=1,2,\ldots$ に対して、項 $a_i$ は塔 $a_i$ に一つのブロックを加える。最初の $N$ 個のブロックを赤いブロックと呼ぶ。 $i>N$ のとき、ブロック $a_i$ は塔 $a_i$ に置かれ、この配置の後のその塔の新しい高さは定義により $a_i$ 自身であり、すなわちブロック $a_i$ はその塔のちょうど高さ $a_i$ の位置に来る——これは $a_i$ が、それまでに $a_{i-1}$ が現れた回数を数えていることを反映している。