MathLabs

第3题

设 a1,a2,a3,…a_1,a_2,a_3,\ldots 是一个由正整数组成的无穷数列，NN 是一个正整数。假设对每个 n>Nn>N，数 ana_n 等于 an−1a_{n-1} 在列表 (a1,a2,…,an−1)(a_1,a_2,\ldots,a_{n-1}) 中出现的次数。证明数列 a1,a3,a5,…a_1,a_3,a_5,\ldots 与 a2,a4,a6,…a_2,a_4,a_6,\ldots 中至少有一个最终是周期性的。
第 4/6 步：最终的小/大交替
上一步下一步
通俗地说

在一个合适的时刻之后，仍在增长的只剩下 L 座无限增长的塔，于是这个过程就会稳定为严格交替：落在这些小塔之一，与落在某个不断变化的大塔之间来回切换。

aN′,aN′+2,…≤L,aN′+1,aN′+3,…>Ma_{N'},a_{N'+2},\ldots\le L,\qquad a_{N'+1},a_{N'+3},\ldots>M
详细分析

由前面的结论，所有标号大于 MM 的塔高度都不超过 MM：每当这样的塔接收一个方块，它的新高度就是下一项；若新高度超过 MM，便会产生两个连续的大于 MM 的项。取 N′>NN'>N，使得有界的塔 L+1,…,ML+1,\ldots,M 已停止接收方块，塔 1,…,L1,\ldots,L 的高度已超过 max⁡(M,N)\max(M,N)，并且 aN′≤La_{N'}\le L；这样的下标存在，因为小项出现无穷多次，而有界的小塔只接收有限多个方块。于是 aN′a_{N'} 是一座增长塔的标号，从而 aN′+1=haN′(N′)>Ma_{N'+1}=h_{a_{N'}}(N')>M。由第3步得 aN′+2≤Ma_{N'+2}\le M，而在 1,…,M1,\ldots,M 中此后仍可能接收方块的只有 1,…,L1,\ldots,L，所以 aN′+2≤La_{N'+2}\le L。反复应用这一论证得到 aN′,aN′+2,aN′+4,…≤La_{N'},a_{N'+2},a_{N'+4},\ldots\le L，以及 aN′+1,aN′+3,aN′+5,…>Ma_{N'+1},a_{N'+3},a_{N'+5},\ldots>M。