Of course, practically, this isn’t a very good thing. In essence, it means that I get to spend nine hours after school taking a mathematics competition when I could be home doing more productive things. And, while it is certainly impressive to have qualified for the USAMO, I somehow doubt it will be all that useful to put that on my résumé.
But it is still very cool to be able to qualify for such a contest, and perhaps – if I am either extremely lucky or much better at math than I thought I was – I will even be in the top six in the nation and make the American IMO team. I would get to go to Vietnam for a week.
Given a sequence S1 of n+1 non-negative integers, a0, a1, … , an we derive another sequence S2 with terms b0, b1, … , bn, where bi is the number of terms preceding ai in S1 which are different from ai (so b0 = 0). Similarly, we derive S2 from S1 and so on. Show that if ai ≤ i for each i, then Sn = Sn+1.
Note that the derived sequence bi also satisfies bi ≤ i (since there are only i terms preceding bi). We show that bi ≥ ai for each i. That is obvious if ai = 0. If ai = k > 0, then since each of the first k terms (a0, a1, … , ak-1) must be i ≥ k.
Next we show that if bi = ai, then further iterations do not change term i. If bi = ai = 0, then none of the terms before ai differ from 0, so all the terms before bi are also 0. But that means the corresponding terms of the next iteration must also all be 0. If bi = ai = k > 0, then since a0, a1, … , ak-1 all differ from ai, the remaining terms (if any) ak, ak+1, … , ai-1 must all be the same as ai. But that implies that each of bk, bk+1, … , bi-1 must also be k. Hence if the next iteration is c0, c1, … then ci = 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.
This will be an… interesting contest. Hopefully I’ll be able to answer at least one of the problems.