Writeup: IMO Shortlist 2001 C5

25 Apr, 2025

Problem Statement:

Find all finite sequences $(x_0,x_1,\dots ,x_n)$ such that for every $j$, $0\le j\le n$, $x_j$ equals the number of times $j$ appears in the sequence.

My Solution:

After attempting A2 today and failing miserably, this problem made me feel better about myself. I felt like this was more of a logic puzzle than anything else.

The first thing I noticed was that $x_0\ne 0$, otherwise we would have a contradiction, and that $\sum x_i=n+1$. I also noticed that giving positive values for $x_i$ where $i$ is a large number "spawns" in a lot of numbers, which could break the summation constraint I just mentioned above.

The key observation to solving this problem is that

where $p$ is the number of nonnegative terms in the sequence.

Now note that we must have $0$ be positive, and there are $p-1$ positive terms from $i=1$ to $n.$ So all the other terms must be $0$, $1$, or $2$. Note that we can only have $x_0$ be a value greater than $2$. So the values we have to inspect are $x_0,x_1,x_2$, and $x_{x_0}$. Note that, if $x_0=1$, then the only sequence that satisfies will be $(1,2,1,0)$. If $x_0=2$, then the only sequence that satisfies these constraints will be $(2,1,2,0,0)$, $(2,0,2,0)$. If $x_0>3$, then we have the sequence $(x_0,2,1,0,\dots ,0,1,0,0,\dots ,0)$, since we must have $x_{x_0}=1$ (if it was 2, then we would have another non-1 and non-2 value with value $x_0$ somewhere else), and we can't have $x_1=1$ otherwise we would have $2$ $1$'s, so we must have $x_2=1$, and therefore we must have $x_1=2$. These are the only solutions so we're done.