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 中至少有一个最终是周期性的。
第 3/6 步：不可能连续出现两个大项
上一步下一步
通俗地说

如果某一项被放到一座已经高于最初 N 座塔中每一座的塔上，追溯这座高高的、全是新方块的塔就会发现，在它之前必定已经有超过 M 座这样更高的塔，而这在第一次发生时就构成矛盾。

an>M  ⟹  an+1≤Ma_n>M\implies a_{n+1}\le M
详细分析

假设第一次出现同时满足 an>Ma_n>M 和 an+1>Ma_{n+1}>M 的情形。方块 BnB_n 位于标号 an>Ma_n>M 的塔中，因此放入它后该塔高度为 an+1>Ma_{n+1}>M，并含有超过 MM 个黄色方块。对每个这样的方块 BrB_r，前一个方块 Br−1B_{r-1} 被放在其所在塔的高度 an>Ma_n>M 处，因为放置方块 Br−1B_{r-1} 后相应塔的高度就是 ana_n。不同的 BrB_r 给出不同的前驱塔，因为同一座塔在同一高度只有一个方块。所以已经有超过 MM 座不同的塔达到大于 MM 的高度。其中必有一座标号为 j>Mj>M，因为标号不超过 MM 的塔只有 MM 座。令 BtB_t 为第一次把塔 jj 从高度 MM 提高到高度 M+1M+1 的方块，则 at=j>Ma_t=j>M 且 at+1=M+1>Ma_{t+1}=M+1>M，并且 t<nt<n，这与 nn 的选取矛盾。因此 an>Ma_n>M 蕴含 an+1≤Ma_{n+1}\le M。于是任意连续两项中至少有一项不超过 MM，从而 1,…,M1,\ldots,M 中某个值出现无穷多次。取最大的 LL 使塔 1,…,L1,\ldots,L 都无限增长；由前面的单射，任何无限增长的塔都会迫使所有更小的塔无限增长，而塔 L+1,…,ML+1,\ldots,M 都有界。