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 中至少有一个最终是周期性的。
第 5/6 步：小项的有限状态描述
上一步下一步
通俗地说

只有那 L 座无限增长的塔之间的相对高度，才决定两步之后的下一个小项，而第 2 步给出的界使这些相对高度只能取有限多种可能。

T(n)=(h1−h2,…,hL−1−hL,an)T(n)=(h_1-h_2,\ldots,h_{L-1}-h_L,a_n)
详细分析

对满足 n≡N′(mod2)n\equiv N'\pmod2 的下标，用放入 BnB_n 后的高度定义 T(n)=(h1−h2,h2−h3,…,hL−1−hL,an)T(n)=(h_1-h_2,h_2-h_3,\ldots,h_{L-1}-h_L,a_n)。我们明确描述两步转移。令 q=hanq=h_{a_n}；由第4步，q=an+1>Mq=a_{n+1}>M。下一个方块放入塔 qq。由于所有标号大于 MM 的塔高度都不超过 MM，放置该方块后下一个小项为 an+2=#{i:hi≥q}a_{n+2}=\#\{i:h_i\ge q\}，其中只有 i=1,…,Li=1,\ldots,L 能作出贡献。这个数量由相对高度决定，因为 qq 是 h1,…,hLh_1,\ldots,h_L 中的一个高度。随后 Bn+2B_{n+2} 使塔 an+2a_{n+2} 的高度增加一，因此所有相邻差与最后一个坐标都由 T(n)T(n) 确定。为证明状态数有限，第2步给出 hk+1≤hk+Ch_{k+1}\le h_k+C；我们还证明当 k<Lk<L 时有 hk≤hk+1+C(L−1)h_k\le h_{k+1}+C(L-1)。若在塔 kk 刚被更新后该不等式失败，则 hk>hk+1+C(L−1)h_k>h_{k+1}+C(L-1)。反复使用 hj≥hj+1−Ch_j\ge h_{j+1}-C 可知 h1,…,hkh_1,\ldots,h_k 中每一个都大于 hk+1,…,hLh_{k+1},\ldots,h_L 中每一个。令 q=hkq=h_k；此时高度至少为 qq 的塔恰好是前 kk 座，因此下一个小项为 kk，同样的两步转移会永远更新塔 kk。这会使塔 k+1,…,Lk+1,\ldots,L 有界，与它们的定义矛盾。所以所有相邻差都落在一个固定有限区间内；再结合 an∈{1,…,L}a_n\in\{1,\ldots,L\}，状态 T(n)T(n) 只有有限多种。