# IMO 2024 PROBLEM 3: Verification required for unconventional solution

Please, can someone verify my (unconventional) solution for P3 Let $$a_1, a_2, a_3, \dots$$ 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, \dots, a_{n-1}$$.

Prove that at least one of the sequence $$a_1, a_3, a_5, \dots$$ and $$a_2, a_4, a_6, \dots$$ is eventually periodic.

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

My Solution: (Sorry, I don't know LaTeX, please excuse me) We have the series a1, a2, a3.... an-1, an, an+1, ... We'll break it down into 2 series, which are interdependent a1, a2, a3.... ,an (S1) and an+1, an+2....(S2) The first sequence is finite, and the second is infinite Let's make a few observations by taking 2 trivial cases; We will not be assuming these cases

1. Say there exists an ar in S2 such that ar=k and k doesn't belong to S1. Then ALL consecutive terms in S2 MUST equal 0. At which point the sequence S2 becomes periodic.

2. Say there exists an ar in S2 such that ar=k and ar appears k times in S1. Then ALL consecutive terms in S2 MUST equal k. At which point the sequence S2 becomes periodic. Now, we define 2 kids of terms:

3. Active terms: Say ar is a term in both S2 and S1. ar is active if a) It repeats some 'k' times and k also lies in S1 AND b) ALL of its successors are also active and have their period lie in S1

4. Dormant terms: Say ar is a term in S2. ar is dormant if a) It repeats some 'k' times and k doesn't lie in S1 OR b) Atleast ONE of its successor's period doesn't lie in S1.

Any term which is part of both an active and a passive group is considered ACTIVE ONLY. example: say p repeats q times, and p and q lie in S1, q repeats r times, r lies in S1, and r repeats s times, where s DOESN'T LIE in S1, then p, q, r and s (and any predecessors of p) are considered dormant.

Notice , if an is a dormant term, then we eventually end up with zeroes, our observation 2. (We essentially assumed an is active.

Claim 1: The active terms form 'chains', with atleast one chain in every possible case of S2 left. In S2, we ALWAYS cycle in the chain which an belongs to.

Before proving, let's define a chain. A chain is a sequence (which say, is some part of S2) b1, b2, b3,.... ,bk-1, bk, bk+1,... br, such that br repeats bk times, which we already know repeats bk+1 times and so on, until the sequence reaches br again and starts repeating again, making it eventually periodic (after bk-1) as defined in the problem.

Proof: Say an doesn't form a chain. This implies there is always a term in the sequence formed by an which has a period of say k, such that k never belongs to the sequence formed by an and k must lie in S1. If I doesn't lie in S1, an becomes dormant. There MUST be infinite, non repeating terms in the sequence formed by an. And ALL of these terms must lie in S1 since an is active. This means S1 must be an infinite sequence, which is an obvious contradiction.

Hence an forms a chain. Every chain is eventually periodic, and an's chain is NOTHING BUT S2!!! THIS MEANS S2 MUST EVENTUALLY BE PERIODIC!!! Which means that the sequences a1, a3, a5.... and a2, a4, a6 must also trivially be periodic. QED

Please verify my proof and spot any obvious mistakes. I am only average at Olympiad math and could make mistakes. Thank you for your time

At the end, you seem to be claiming that both $$a_1, a_3, \ldots$$ and $$a_2, a_4, \ldots$$ are eventually periodic, which is false. For example, consider the sequence 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, ... It satisfies the condition (with $$N=1$$) but only $$a_1, a_3, \ldots$$ is eventually periodic. And $$S_2$$ is not eventually periodic in this case.