MathLabs

Problem 3

Let a1,a2,a3,…a_1,a_2,a_3,\ldots be an infinite sequence of positive integers, and let NN be a positive integer. Suppose that, for each n>Nn>N, the number ana_n is equal to the number of times an−1a_{n-1} appears in the list (a1,a2,…,an−1)(a_1,a_2,\ldots,a_{n-1}). Prove that at least one of the sequences a1,a3,a5,…a_1,a_3,a_5,\ldots and a2,a4,a6,…a_2,a_4,a_6,\ldots is eventually periodic.
Step 4 of 6: An eventual small/big alternation
Previous stepNext step
In plain words

Past a suitable point, the only towers still growing are the L unbounded ones, so the process settles into strictly alternating between landing on one of these small towers and landing on some large, ever-changing tower.

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
Detailed analysis

After the previous claim, every tower with label greater than MM has height at most MM: whenever such a tower receives a block, its new height is the next term, and a height greater than MM would create two consecutive terms greater than MM. Choose N′>NN'>N after all bounded towers L+1,…,ML+1,\ldots,M have stopped receiving blocks, after towers 1,…,L1,\ldots,L have height greater than max⁡(M,N)\max(M,N), and with aN′≤La_{N'}\le L; such indices exist because small terms occur infinitely often and the bounded small towers occur only finitely often. Then aN′a_{N'} is a growing-tower label, so aN′+1=haN′(N′)>Ma_{N'+1}=h_{a_{N'}}(N')>M. The implication from Step 3 forces aN′+2≤Ma_{N'+2}\le M, and since the only towers among 1,…,M1,\ldots,M that can still receive blocks are 1,…,L1,\ldots,L, it follows that aN′+2≤La_{N'+2}\le L. Repeating this argument gives aN′,aN′+2,aN′+4,…≤La_{N'},a_{N'+2},a_{N'+4},\ldots\le L and aN′+1,aN′+3,aN′+5,…>Ma_{N'+1},a_{N'+3},a_{N'+5},\ldots>M.