IMO 1997 SL 2

Origin: CAN

Problem

Let R1, R2, . . . be the family of finite sequences of positive inte- gers defined by the following rules: R1 = (1), and if Rn−1 = (x1, . . . , xs), then Rn = (1, 2, . . . , x1, 1, 2, . . ., x2, . . . , 1, 2, . . . , xs, n). For example, R2 = (1, 2), R3 = (1, 1, 2, 3), R4 = (1, 1, 1, 2, 1, 2, 3, 4). Prove that if n > 1, then the kth term from the left in Rn is equal to 1 if and only if the kth term from the right in Rn is different from 1.

Solution

For any sequence X = (x1, x2, . . . , xn) let us define X = (1, 2, . . . , x1, 1, 2, . . ., x2, . . . , 1, 2, . . . , xn). Also, for any two sequences A, B we denote their concatenation by AB. It clearly holds that AB = A B. The sequences R1, R2, . . . are given by R1 = (1) and Rn = Rn−1(n) for n > 1. We consider the family of sequences Qni for n, i \inN, i \leqn, defined as follows: Qn1 = (1), Qnn = (n), and Qni = Qn−1,i−1Qn−1,i if 1 < i < n. These sequences form a Pascal-like triangle, as shown in the picture below: Q1i : Q2i : Q3i : Q4i : Q5i : 1112 112123 1234

We claim that Rn is in fact exactly Qn1Qn2 . . . Qnn. Before proving this, we observe that Qni = Qn−1,i. This follows by induction, because Qni = Qn−1,i−1Qn−1,i = Qn−2,i−1 Qn−2,i = Qn−1,i for n \geq3, i \geq2 (the cases i = 1 and n = 1, 2 are trivial). Now R1 = Q11 and Rn = Rn−1(n) = Qn−1,1 . . . Qn−1,n−1(n) = Qn,1 . . . Qn,n−1Qn,n for n \geq2, which justifies our claim by induction. Now we know enough about the sequence Rn to return to the question of the problem. We use induction on n once again. The result is obvious for n = 1 and n = 2. Given any n \geq3, consider the kth elements of Rn from the left, say u, and from the right, say v. Assume that u is a member of Qnj, and consequently that v is a member of Qn,n+1−j. Then u and v come from symmetric positions of Rn−1 (either from Qn−1,j, Qn−1,n−j, or from Qn−1,j−1, Qn−1,n+1−j), and by the inductive hypothesis exactly one of them is 1.