IMO 2001 SL C5

Origin: FIN | Category: Combinatorics

Problem

Find all finite sequences (x0, x1, . . . , xn) such that for every j, 0 \leqj \leqn, xj equals the number of times j appears in the sequence.

Solution

Let (x0, x1, . . . , xn) be any such sequence: its terms are clearly nonnegative integers. Also, x0 = 0 yields a contradiction, so x0 > 0. Let m be the number of positive terms among x1, . . . , xn. Since xi counts the terms equal to i, the sum x1 +\cdot \cdot \cdot+xn counts the total number of positive terms in the sequence, which is known to be m + 1. Therefore among x1, . . . , xn exactly m −1 terms are equal to 1, one is equal to 2, and the others are 0. Only x0 can exceed 2, and consequently at most one of x3, x4, . . . can be positive. It follows that m \leq3. (i) m = 1: Then x2 = 2 (since x1 = 2 is impossible), so x0 = 2. The resulting sequence is (2, 0, 2, 0). (ii) m = 2: Either x1 = 2 or x2 = 2. These cases yield (1, 2, 1, 0) and (2, 1, 2, 0, 0) respectively. (iii) m = 3: This means that xk > 0 for some k > 2. Hence x0 = k and xk = 1. Further, x1 = 1 is impossible, so x1 = 2 and x2 = 1; there are no more positive terms in the sequence. The resulting sequence is (p, 2, 1, 0, . . ., 0    p−3 , 1, 0, 0, 0).