第3题

设

a_1,a_2,a_3,\ldots

是一个由正整数组成的无穷数列，

N

是一个正整数。假设对每个

n>N

，数

a_n

等于

a_{n-1}

在列表

(a_1,a_2,\ldots,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}$ 出现过的次数。