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 中至少有一个最终是周期性的。
第 2/6 步：相邻的塔不会相差太远
上一步下一步
通俗地说

每当塔 k+1 从这个过程中获得一个新方块，这一事件都可以通过一条短的、单射的早期方块链追溯到塔 k 中相应的一个新方块，因此塔 k 永远不会比塔 k+1 落后太多。

hk≥hk+1−Ch_k\ge h_{k+1}-C
详细分析

记 BiB_i 为对应于 aia_i 的方块，并把它放在标号为 aia_i 的塔中。当 i>Ni>N 时，按定义 BiB_i 的高度为 ai+1a_{i+1}，因为 ai+1a_{i+1} 统计的是此前标号 aia_i 出现的次数。固定 kk。若 BnB_n 是塔 k+1k+1 中的黄色方块，则 an=k+1a_n=k+1，所以 Bn−1B_{n-1} 是其所在塔中高度为 k+1k+1 的方块。除去与最初红色方块有关的有限多个例外，Bn−1B_{n-1} 正下方的方块也是黄色的，记为 BrB_r。它的高度为 kk，故规则给出 ar+1=ka_{r+1}=k，于是 Br+1B_{r+1} 位于塔 kk 中。因此，除去有限个例外，可以把塔 k+1k+1 中的每个黄色方块 BnB_n 映射到这个 Br+1B_{r+1}。该映射是单射：不同的 BnB_n 给出不同的 Bn−1B_{n-1}，继而给出不同的正下方方块，最后给出不同的后继方块。所以在任一时刻，塔 k+1k+1 中黄色方块的数目至多是塔 kk 中方块数加上一个固定的例外数。把有限个红色方块吸收到只依赖于 NN 与 MM 的常数 CC 中，得到 hk≥hk+1−Ch_k\ge h_{k+1}-C。特别地，一座塔若无限增长，则紧邻其左侧的塔也无限增长。