IMO 2024 · Problem 3

Let \(a_1,a_2,a_3,\ldots\) be an infinite sequence of positive integers, and let \(N\) be a positive integer. Suppose that, for each \(n>N\), \(a_n\) is equal to the number of times \(a_{n-1}\) appears in the list \(a_1,a_2,\ldots,a_{n-1}\).

Prove that at least one of the sequences \(a_1,a_3,a_5,\ldots\) and \(a_2,a_4,a_6,\ldots\) is eventually periodic.

(An infinite sequence \(b_1,b_2,b_3,\ldots\) is eventually periodic if there exist positive integers \(p\) and \(M\) such that \(b_{m+p}=b_m\) for all \(m\ge M\).)

Official text of the problem. Official problem paper (PDF)

Solution

For a positive integer \(x\), write \[ C_x(n)=\#\{j\le n:a_j=x\}. \] The given rule says that \[ a_{n+1}=C_{a_n}(n)\qquad(n\ge N). \] Consequently, no ordered pair \((x,y)\) occurs twice as \((a_n,a_{n+1})\) with \(n\ge N\): at successive occurrences of \(x\), its occurrence count strictly increases.

Set \[ B=\max(a_1,\ldots,a_N). \] Call a term small if it is at most \(B\), and large otherwise.

We first prove that two large terms cannot be consecutive. Suppose otherwise, and let \(a_t,a_{t+1}\) be the first such pair. Every occurrence of the value \(a_t\) among \(a_1,\ldots,a_t\) is after position \(N\) and is preceded by a small term. These preceding terms must be distinct, since an ordered pair cannot repeat. Thus \(a_t\) has occurred at most \(B\) times, giving \[ a_{t+1}=C_{a_t}(t)\le B, \] a contradiction.

The same observation shows that each large value occurs at most \(B\) times in the entire sequence: every occurrence is preceded by one of the \(B\) small values, and each such ordered pair occurs at most once.

There are also only finitely many consecutive pairs of small terms, because there are only \(B^2\) possible ordered pairs of small values. Hence, from some point onward, the sequence alternates between small and large terms.

Let \(S\) be the set of small values occurring infinitely often, and put \(k=|S|\). The alternation shows that \(k\ge1\). Choose \(L\ge N\) so that every small term at a position at least \(L\) belongs to \(S\), and set \[ H=\max(B,L). \] Every term among \(a_1,\ldots,a_L\) is at most \(H\): the first \(N\) terms are at most \(B\), and \(a_n\le n-1\) for \(n>N\).

Consider any integer \(y>H\). Every occurrence of \(y\) is after position \(L\) and is preceded by a member of \(S\). Conversely, for each \(x\in S\), the \(y\)-th occurrence of \(x\) is after position \(L\), and its successor is \(y\). Thus \(y\) occurs exactly \(k\) times, once following each member of \(S\).

The successors of these \(k\) occurrences of \(y\), in chronological order, are \(1,2,\ldots,k\). Since there are infinitely many choices of \(y>H\), each of \(1,2,\ldots,k\) occurs infinitely often. As \(S\) has exactly \(k\) members, we obtain \[ S=\{1,2,\ldots,k\}. \]

Each large value occurs only finitely often, so the large terms tend to infinity. We may therefore choose a tail of the form \[ b_0,h_0,b_1,h_1,b_2,h_2,\ldots, \] where \[ b_t\in\{1,\ldots,k\},\qquad h_t>H, \] and every value \(1,\ldots,k\) occurs infinitely often among the \(b_t\).

We will prove that \((b_t)\) is eventually periodic. If \(k=1\), this is immediate, so assume \(k\ge2\).

For \(1\le i\le k\), let \(q_i(t)\) be the number of occurrences of \(i\) strictly before the displayed term \(b_t\). Let \(e_i\) denote the \(i\)-th unit vector. Then \[ q(t+1)=q(t)+e_{b_t}, \qquad h_t=q_{b_t}(t+1). \tag{1} \] Every occurrence of \(h_t\) follows the \(h_t\)-th occurrence of exactly one member of \(\{1,\ldots,k\}\). By the time the displayed \(h_t\) has appeared, this has happened for precisely those \(i\) satisfying \(q_i(t+1)\ge h_t\). Therefore \[ b_{t+1} =\#\{i:q_i(t+1)\ge q_{b_t}(t+1)\}. \tag{2} \]

We now establish that the differences between the coordinates of \(q(t)\) remain bounded.

Let \[ s_1(t)\ge s_2(t)\ge\cdots\ge s_k(t) \] be the coordinates of \(q(t)\), sorted in decreasing order. When an integer coordinate increases from \(v\) to \(v+1\), the sorted vector increases by \(1\) at exactly position \[ 1+\#\{\text{coordinates previously greater than }v\}. \] This position is the number of coordinates at least \(v+1\) after the increase. By (2), it is \(b_{t+1}\). Hence \[ s(t+1)=s(t)+e_{b_{t+1}}. \] Together with (1), this gives the invariant \[ q(t)-s(t)+e_{b_t}=d, \tag{3} \] where \(d=q(0)-s(0)+e_{b_0}\) is fixed.

Choose the positive integer \[ D=1+\max_{1\le i\le k}|d_i|. \] Equation (3) implies \[ |q_i(t)-s_i(t)|\le D \qquad\text{for every }i,t. \tag{4} \] Define \[ G=\max\bigl(2D,\ s_1(0)-s_2(0),\ldots,s_{k-1}(0)-s_k(0)\bigr). \] We claim that \[ s_r(t)-s_{r+1}(t)\le G \qquad(1\le r<k,\ t\ge0). \tag{5} \]

Suppose (5) fails for some \(r\), and let \(t\) be the first time that this particular gap exceeds \(G\). The gap must have increased at this step, so the sorted coordinate that increased was \(s_r\). Thus \(b_t=r\). Moreover, for every \(i\le r<j\), (4) gives \[ q_i(t)-q_j(t) \ge s_r(t)-s_{r+1}(t)-2D >0. \tag{6} \] In other words, all coordinates with labels \(1,\ldots,r\) are strictly larger than all remaining coordinates.

Now \(b_t=r\), so the next step increases one of the first \(r\) coordinates. Their strict separation from the remaining coordinates persists. Formula (2) then gives \(b_{t+1}\le r\). Repeating this argument shows that \[ b_u\le r\qquad\text{for all }u\ge t. \] This contradicts the fact that every value \(1,\ldots,k\) occurs infinitely often among the \(b_u\). Thus (5) holds.

It follows that \[ \max_i q_i(t)-\min_i q_i(t) =s_1(t)-s_k(t) \le(k-1)G. \tag{7} \]

Finally, put \(m(t)=\min_i q_i(t)\), and consider the state \[ \bigl(b_t,\ q_1(t)-m(t),\ldots,q_k(t)-m(t)\bigr). \] By (7), this state has only finitely many possibilities. Equations (1) and (2) determine its next value uniquely: adding the same integer to all coordinates of \(q(t)\) changes neither the comparisons in (2) nor the normalized coordinates at the next step.

Thus we have a deterministic sequence of states in a finite set. Some state repeats, and from that point onward the states—and therefore the values \(b_t\)—are periodic.

The terms \(b_t\) occupy every other position in the original sequence. Consequently, one of its odd-indexed and even-indexed subsequences is eventually periodic, as required. \(\square\)

The solution was checked against the official IMO shortlist solutions.