USAMO 03/A3 solution

33rd USAMO 2003

Problem A3

Given a sequence S₁ of n+1 non-negative integers, a₀, a₁, ... , a_n we derive another sequence S₂ with terms b₀, b₁, ... , b_n, where b_i is the number of terms preceding a_i in S₁ which are different from a_i (so b₀ = 0). Similarly, we derive S₂ from S₁ and so on. Show that if a_i ≤ i for each i, then S_n = S_n+1.

Solution

Note that the derived sequence b_i also satisfies b_i ≤ i (since there are only i terms preceding b_i). We show that b_i ≥ a_i for each i. That is obvious if a_i = 0. If a_i = k > 0, then since each of the first k terms (a₀, a₁, ... , a_k-1) must be < k, we certainly have b_i ≥ k.

Next we show that if b_i = a_i, then further iterations do not change term i. If b_i = a_i = 0, then none of the terms before a_i differ from 0, so all the terms before b_i are also 0. But that means the corresponding terms of the next iteration must also all be 0. If b_i = a_i = k > 0, then since a₀, a₁, ... , a_k-1 all differ from a_i, the remaining terms (if any) a_k, a_k+1, ... , a_i-1 must all be the same as a_i. But that implies that each of b_k, b_k+1, ... , b_i-1 must also be k. Hence if the next iteration is c₀, c₁, ... then c_i = k also.

Now we use induction on k. Clearly term 0 is always 0. Considering the two cases, we see that term 1 does not change at iteration 1. So suppose that term i does not change at iteration i. If term i+1 does change at iteration i+1, then it must have changed at all previous iterations. So it must have started at 0 and increased by 1 at each iteration.

33rd USAMO 2003