Problem 3 from the 2024 IMO (International Math Olympiad):
Let a1, a2, a3, . . . be an infinite sequence of positive integers, and let N be
a positive integer. Suppose that, for each n, a(n) is equal to the number of times a(n-1) appears in the list {a1, a2, . . . , a{n-1)}.
Prove that at least one of the sequences a1, a3, a5, . . . and a2, a4, a6, . . . is eventually periodic.
(An infinite sequence b1, b2, b3, . . . is eventually periodic if there exist positive integers p and M such that b(m) = b(m+p) for all m greater than M.)
(proposed by Australia)
0:00 Introduction
0:45 Playing with the Sequence
2:20 Observations
4:12 Understanding the Sequence
9:38 Proof
Link to written explanation:
[ Ссылка ]
I apologise if there are any errors or oversights, feel free to raise these in the comments.
The official IMO 2024 solutions contain two alternative proofs, both of which are quite different (and certainly more rigorous) than the one I have shown here.
[ Ссылка ]
The video solution by the excellent channel
@dedekindcuts3589 also presents another different and very thorough method.
