第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

中至少有一个最终是周期性的。

第 6/6 步：鸽笼原理迫使最终周期性

上一步下一步

通俗地说

由于可用状态只有有限多个，且有一条确定性规则每次把状态推进两个下标，状态序列最终必定重复出现某个值，此后一切都会永远循环。

T(n)=T(n')\implies a_n,a_{n+2},\ldots \text{ periodic from that point}

详细分析

由于 $T(n)$ 在 $n$ 取遍 $N',N'+2,N'+4,\ldots$ 时只能取有限多个值（第 5 步），且 $T(n+2)$ 是 $T(n)$ 的一个确定性函数，由鸽笼原理，某个状态会重复出现，即存在 $n<n'$ 且 $n\equiv n'\pmod2$ 使得 $T(n)=T(n')$ ；从那时起状态以周期 $n'-n$ 循环，特别地对应的子列 $a_n$ （固定奇偶性的下标）最终是周期性的。由于 $N'$ 的奇偶性是确定的，这说明两个子列 $a_1,a_3,a_5,\ldots$ 与 $a_2,a_4,a_6,\ldots$ 中至少有一个最终是周期性的。