Find all finite sequences a0, a1, a2, ... , an such that am equals the number of times that m appears in the sequence.
Solution
Answer: (1) 1, 2, 1, 0; (2) 2, 0, 2, 0; (3) 2, 1, 2, 0, 0; (4) N, 2, 1, 0, ... , 0 with N+4 terms, except that aN = 1.
Note that we cannot have a0 = 0. Suppose there are k other non-zero terms. The number of 1s is a1, the number of 2s is a2 etc, so the number of non-zero terms is a1 + a2 + ... + an. Hence a1 + a2 + ... + an = k+1. But if there are k+1 non-zero terms, then k of a1, a2, ... , an are at least 1. So k-1 of them must be 1, one of them 2 and the rest 0. In particular, none of them are 3 or more (*).
If a0 is 1 or 2, then no member of the sequence is 3 or more, so a3 = ... = an = 0.
Suppose a0 = 1. Then a1 cannot be 1 (or there would be two 1s). It cannot exceed 2, so it must be 2. But the only other term that can be 1 is a2, so a2 = 1. We need a 0, so a3 = 0. There cannot be any further terms, because they would have to be 0s and we have enough already. Thus we have the solution 1, 2, 1, 0.
Suppose a0 = 2. We know that a1 cannot exceed 2. Suppose it is 2. Then a2 is at least 2. Like all the terms, it is at most 2. But if it is 2, then there are three 2s. Contradiction. So a1 must be 0 or 1. Suppose it is 0. Then a2 is at least 1 because a0 is 2. But it cannot be 1, because there are no 1s. So it must be 2. So all remaining terms must be 0. Now there are two 0s, so there must be just one more term, and we have the solution 2, 0, 2, 0.
So suppose a1 = 1 (and a0 = 2). Again there are no more 1s. So a2 must be 2. Hence all remaining terms must be 0. We need two more 0s (to get a0 correct), so we have the solution 2, 1, 2, 0, 0.
That exhausts the possibilities for a0 = 1 or 2. So suppose a0 = N > 2. Hence aN = 1. So a1 is at least 1. It cannot be 1 (or there would be two 1s). But by (*) it cannot exceed 2, so it must be 2. Hence, by (*), a2 must be 1. Since the only term exceeding 2 is a0 (by (*) ), all of a3, a4, ... , an except aN must be 0. We need N zeros, so n = N+3. It is easy to check that a0 = N (> 2), a1 = 2, a2 = 1, aN = 1 and the rest of a3, a4, ... , aN+3 is indeed a solution.
© John Scholes
jscholes@kalva.demon.co.uk
14 Oct 2002