# IMO 2024 p-3,Sequence of Counts - Are Odd or Even Terms Eventually Periodic?

Let $$a_1, a_2, a_3, \dots$$ be an infinite sequence of positive integers, and let $$N$$ be a positive integer. We define $$a_n$$ for $$n > N$$ as the number of times $$a_{n-1}$$ appears in the list $$a_1, a_2, \dots, a_{n-1}$$.

prove that at least one of the sequences $$a_1, a_3, a_5, \dots$$ or $$a_2, a_4, a_6, \dots$$ is eventually periodic.

Attempt:

The sequence starts with a finite number of terms. For $$n > N$$, $$a_n$$ counts occurrences of $$a_{n-1}$$ There are only finitely many positive integers. This implies that as $$n$$ grows, $$a_n$$ must repeat some earlier values due to the limited range of counts. Consider the odd-indexed terms $$b_n = a_{2n-1}$$ and the even-indexed terms $$c_n = a_{2n}$$. Since both sequences are derived from the same rules, if one sequence stabiliz, the other is influenced by it Eventually, if either sequence starts repeating values it indicates periodic behavior because the defining relationship relies on past terms leading to cycles

maybe the pigeonhole principle will be helpful?

any help is appreciated

• "There are only finitely many positive integers"??? Commented Jul 16 at 18:05
• Based on your title, this appears to be a question from the ongoing IMO 2024 competition. imo2024.uk If this is the case, I implore everyone not to answer this question. Commented Jul 16 at 18:19
• @MikeEarnest No, since Day 1 is over, we can discuss the problems now.The problem appeared on Day 1 and is also posted on AoPS, but there are still no answers. The other two problems have been solved. Commented Jul 16 at 18:28
• @MikeEarnest In order to apply the Math SE procedure regarding competition problems, we need (a) a publicly viewable set of problems, and (b) a link to a set of rules forbidding outside help. Commented Jul 16 at 18:55

Solution

Interesting combinatorics in disguise of sequence. The key is to prove that sufficiently large numbers appear finitely many times in such sequence, and such number of appearance should be equal for all sufficiently large numbers.

Denote $$f(n, i)$$ the number of occurrences of $$i$$ among the first $$n$$ entries $$a_1, \ldots, a_n$$ of the sequence. We have $$a_n = f(n-1, a_{n-1})$$ for all $$n > N$$. Select a sufficiently large integer $$M > N$$ such that $$f(N, j) = 0$$ for all $$j \ge M$$ and $$f(N, j) < M$$ for all $$j .

We begin by observing that starting from $$n = N+1$$, any pairs $$(a_n, a_{n+1})$$ will appear only once in the sequence. It means that all the numbers that precedents a same number $$j$$ in the sequence must be mutually different.

Claim 1: For all $$t > N$$ and $$M \le i < j$$, $$f(t, i) \ge f(t, j)$$.

Proof: WLOG assume that $$j = i+1$$. For any $$t > N$$, note that since $$f(N, j) = f(N, i) = 0$$, all occurrences of $$i$$ and $$j$$ must be in $$a_{N+1}, \ldots, a_t$$. Let $$i_1, \ldots, i_{f(t, j)}$$ be the indices such that $$a_{i_l} = j$$ for $$1\le l \le f(t, j)$$, then we have $$f(i_l - 1, a_{i_l - 1}) = j$$. There must then exist $$k_l < i_l-1$$ such that $$f(k_l, a_{i_l - 1}) = i$$ and $$a_{k_l} = a_{i_l-1}$$ , and thus $$a_{k_l+1} = i$$. Note that all $$a_{i_l-1}$$ should be mutually different, so all $$k_l$$ are mutually different. So $$i$$ occurs at least as many times as $$j$$ within $$a_1, \ldots, a_t$$. This implies $$f(t, i) \ge f(t, j)$$.

Claim 2: $$f(t, K)\le K-1$$ for all $$t$$.

Proof Assume the contradiction and consider the indice $$t$$ such that $$a_t = K$$ and $$f(t, K) = K$$. Let $$i_1 be the indices such that $$a_{i_l} = K$$. Note that all $$a_{i_l-1}$$ must be mutually different, so one of $$a_{i_l-1}$$ is greater than $$K$$. Then, $$f(i_l-1, a_{i_l-1}) = K > f(t-1, K) \ge f(i_l-1, K)$$, contradicts claim 1.

Due to claim 1 and claim 2, for all $$t$$ and $$i \ge K$$, we have $$f(t, i) \le K-1$$. This means that for any given $$i$$, $$\lim_{t\to \infty} f(t, i)$$ converges to $$B_i$$ for some $$B_i \le K-1$$ (due to monotonicity in $$t$$). Due to claim 1 again we can see that $$B_i\ge B_j$$ for all $$K\le i < j$$, so $$\lim_{i\to \infty} B_i = c$$ for some $$0\le c \le K-1$$. Hence, there exists constants $$T, M, c$$ such that $$f(t, i) = c$$ for all $$t > T, i > M$$.

Claim 3: $$c \ge 1$$ and the numbers $$1, 2, \ldots, c$$ are the only numbers that occur infinitely often in the sequence.

Proof: To show that $$c \ge 1$$ it is sufficient to show that any number $$x$$ must occur once in the sequence $$(a_n)$$. Note that there must exist a number $$a$$ that occurs infinitely many times in the sequence. Let $$l$$ be the indices of its $$x^\text{th}$$ occurrence, then $$a_{l+1} = x$$, as desired.

Now it is obvious to see that $$1, 2, \ldots, c$$ occur infinitely often in the sequence. We show that any $$i > c$$ does not occur infinitely often. Assume the contradiction, then since for all $$j > M$$, $$f(t, j)$$ is eventually $$c$$, or $$f(t, j)$$ will occur only $$c$$ times in the sequence, then after the occurrence of $$j$$ it can only be the numbers from $$1, 2, \ldots, c$$. This means that the occurrence of $$i > c$$ can only be after a number $$j' < M$$. Since there are only finitely many such $$j'$$, the occurrence of $$i$$ must be finite.

Claim 3 implies that there exists sufficiently large integers $$N'$$ and $$M$$ such that for all $$n > N'$$, it is either that $$a_n > M$$, or $$a_n \le c$$. Note that we can again select $$N'$$ to be large enough so that $$f(N', i) > c$$ for all $$1\le i \le c$$, so that any numbers that comes after $$1\le i \le c$$ must be larger than $$M$$. This creates an alternating sequence between "large" and "small" number. It is sufficient to show that the sequence of "small" number is eventually periodic. The tricky part of this is to control the gap between occurrences of the same number.

Claim 4: There exists a constant $$D$$ such that for any $$t$$, $$\max_{1\le i \le c} f(t, i) - \min_{1\le i\le c} f(t, i) \le D$$.

Proof: For any $$1\le x < y\le c$$, there is a constant $$L_{x, y}$$ for any $$t$$, $$f(t, x) \ge f(t, y) - L_{x, y}$$. Note that when $$t > N'$$, any occurrences of $$y$$ must be precedented by an occurrence of a number $$j > M$$. Such $$j > M$$ must give an occurrence of $$x < y$$ some time before that.

Let $$L = \max(L_{x, y})$$ over all $$x < y$$. Then, if we assume the contradiction that $$\max_{1\le i \le c} f(t, i) - \min_{1\le i\le c} f(t, i)$$ is not uniformly bounded on $$t$$, then there must be a sufficiently large $$t$$ and an $$1\le i \le c-1$$ such that $$\min_{1\le j \le i} f(t, j) > \max_{i+1\le j \le c} f(t, j)$$. In fact, let $$t$$ be the number such that $$\max_{1\le i \le c} f(t, i) - \min_{1\le i\le c} f(t, i) > 3L$$. Let $$j_1, j_2$$ be the indices that $$f(t, j_1) = \max_{1\le i\le c} f(t, i), f(t, j_2) = \min_{1\le i\le c} f(t, i)$$. By claim 3, we must have $$j_1 < j_2$$. Furthermore, $$f(t, i) \ge f(t, j_1) - L$$ for all $$i < j_1$$, and $$f(t_i) \le f(t, j_2) + L$$ for all $$i > j_2$$. Since there can't be $$j_1 < k_1 < k_2 < j_2$$ such that $$f(t, k_2) \ge f(t, j_1) - L$$ and $$f(t, k_1) \le f(t, j_2) + L$$, it must be the case that there is an index $$k$$ such that $$f(t, i) \ge f(t, j_1) - L)$$ for all $$i \le k$$, and $$f(t, i) \le f(t, j_2) + L$$ for all $$i > k$$. Since $$f(t, j_1) - L > f(t, j_2) + L$$, we arrive at the claim.

Then, at the first time $$t$$ that this happens, $$a_t \le i$$, and $$a_{t+1}$$ is larger than $$\max_{i+1\le j \le c} f(t, j)$$. Then, $$a_{t+2}$$ must be in $$1, 2, \ldots, i$$, and we can use induction to show that from then on, no more occurrences of $$i+1, \ldots, c$$ can happen, which contradicts claim 3.

For a number $$n > M$$, define $$i_{n, 1} < i_{n, 2} < \ldots < i_{n, c}$$ the indices that $$a_{i_{n, k}} = n$$. Denote the difference tuple $$T_n = (i_{n, 2} - i_{n, 1}, \ldots, i_{n, c} - i_{n, c-1})$$.

Claim 5: There is a constant $$D'$$ such that $$i_{n, h} - i_{n, h-1} \le D'$$ for all $$n > M$$ and $$2\le h\le c$$.

Proof: Note that the difference between $$f(t, i)$$ and $$f(t, j)$$ for $$1\le i < j\le c$$ is bounded above by $$D$$ at any time $$t$$ (claim 4). Consider $$a_{i_{n, h-1}} = n, a_{i_{n, h-1}+1} = h-1$$ and $$a_{i_{n, h}} = n, a_{i_{n, h}+1} = h$$. Note that for $$i_{n, h-1} \le t \le i_{n, h}-2$$, among $$f(t, 1), \ldots, f(t, c)$$, there are exactly $$h-1$$ values that are at least $$n$$, and all other values must be smaller than $$n$$. As the gap between the maximum and minimum of $$f(t, i)$$ is at most $$D$$, we can see that the values initially smaller than $$n$$ must be at least $$n-D$$, and thus the appearance of $$a$$ such that $$f(i_{n, h-1}, a) < n$$ between $$i_{n, h-1} \le t \le i_{n, h}-2$$ can only be at most $$D$$. Likewise, the appearance of $$a$$ such that $$f(i_{n, h-1}, a) \ge n$$ between $$i_{n, h-1} \le t \le i_{n, h}-2$$ is also at most $$D$$, as $$f(t, a)$$ can only increase at maximal to $$n+D$$.

This implies a rough bound $$i_{n, h} - i_{n, h-1} \le 2Dc$$. Let $$D' = 2Dc$$ and we are done.

Now, since there are at most $$D'^{c-1}$$ values for the tuples $$T_n$$ for $$n \ge M$$, $$T_n$$ must be eventually periodic. Let $$T$$ be the period of $$T_n$$, and let $$b = i_{n+T, 1} - i_{n, 1}$$, then for every sufficiently large $$n$$ and $$1\le h\le c$$, we have $$i_{n+T, h} - i_{n, h} = i_{n+T, H} - i_{n+T, 1} - (i_{n, h} - i_{n, 1}) + i_{n+T,1} - i_{n, 1} = i_{n+T,1} - i_{n, 1}$$. Now, we can proceed similar to claim 5 to show that there is a constant $$B$$ such that $$i_{n+T,1} - i_{n, 1} \le B$$ for all $$n$$ (brief idea: the difference $$i_{n+T,1} - i_{n, 1}$$ is the difference between the $$n^\text{th}$$ 1 and $$(n+T)^\text{th}$$ 1, hence occurrences of $$2, \ldots, c$$ can only be at most $$T+2D$$ for each of them). This again means that $$i_{n+T,1} - i_{n, 1} \le B$$ is eventually periodic, so there is a period $$C$$ such that $$i_{n+T+C,1} - i_{n+C, 1} = i_{n+T,1} - i_{n, 1}$$ for all $$n$$ sufficiently large.

It is important to note that eventual periodicity is implied due to a non trivial fact that once a pattern repeats, then by induction it will keep repeating. I'll leave this as some details for others to work on.

Let $$b = i_{n+T+C, 1} - i_{n, 1}$$. Then for any $$n$$ sufficiently large and $$1\le h\le c, a_{i_{n, h} +1} = h = a_{i_{n+T+C, h} + 1} = a_{i_{n, h} + b+1}$$. This implies that the "small" sequence is eventually periodic, as desired.

Due to my laziness, I might have avoided many small details of the proof. Any comments are appreciated.

I believe this is truly a combinatorics problem despite looking like algebra, but most of the core arguments are playing around with combinatorial arguments of occurrences of numbers. Algebraic formulation is for better readability. One of my friends have another combinatorial formulation that might be easier to argue on: assume that you have infinite bags of marbles that are labelled $$1,2,3, \ldots$$. At the beginning, you randomly put marbles into the bag, but after time $$N$$, if the last marble is placed into a bag with $$k-1$$ marbles, then you place the next marble into the bag $$k$$.