IMO 1989 SL 23

Origin: POL

Problem

We consider permutations (x1, . . . , x2n) of the set {1, . . . , 2n} such that |xi −xi+1| = n for at least one i \in{1, . . ., 2n−1}. For every natural number n, find out whether permutations with this property are more or less numerous than the remaining permutations of {1, . . . , 2n}.

Solution

Two numbers x, y \in{1, . . . , 2n} will be called twins if |x −y| = n. Then the set {1, . . . , 2n} splits into n pairs of twins. A permutation (x1, . . . , x2n) of this set is said to be of type Tk if |xi −xi+1| = n holds for exactly k indices i (thus a permutation of type T0 contains no pairs of neigh- boring twins). Denote by Fk(n) the number of Tk-type permutations of {1, . . . , 2n}. Let (x1, . . . , x2n) be a permutation of type T0. Removing x2n and its twin, we obtain a permutation of 2n −2 elements consisting of n −1 pairs of twins. This new permutation is of one of the following types:

(i) type T0: x2n can take 2n values, and its twin can take any of 2n −2 positions; (ii) type T1: x2n can take any one of 2n values, but its twin must be placed to separate the unique pair of neighboring twins in the new permutation. The recurrence formula follows: F0(n) = 2n[(2n −2)F0(n −1) + F1(n −1)]. (1) Now let (x1, . . . , x2n) be a permutation of type T1, and let (xj, xj+1) be the unique neighboring twin pair. Similarly, on removing this pair we get a permutation of 2n −2 elements, either of type T0 or of type T1. The pair (xj, xj+1) is chosen out of n twin pairs and can be arranged in two ways. Also, in the first case it can be placed anywhere (2n −1 possible positions), but in the second case it must be placed to separate the unique pair of neighboring twins. Hence, F1(n) = 2n[(2n −1)F0(n −1) + F1(n −1)] = F0(n) + 2nF0(n −1). (2) This implies that F0(n) < F1(n). Therefore the permutations with at least one neighboring twin pair are more numerous than those with no such pairs. Remark 1. As in the official solution, formulas (1) and (2) together give for F0 the recurrence F0(n) = 2n[(2n −1)F0(n −1) + (2n −2)F0(n −2)]. For the ratio pn = F0(n)/(2n)!, simple algebraic manipulation yields pn = pn−1 + pn−2 (2n−3)(2n−1). Since p1 = 0, we get pn < pn−1 + (2n −3)(2n −1) = pn−1 + 2(2n −3) − 2(2n −1) < \cdot \cdot \cdot < 1 2. Remark 2. Using the inclusion–exclusion principle, the following formula can be obtained: F0(n) = 20 n  (2n)! −21 n  (2n −1)! + 22 n  (2n −2)! −\cdot \cdot \cdot \cdot \cdot \cdot + (−1)n−12n n n  n!. One consequence is that in fact, limn\to\inftypn = 1/e. Second solution. Let f : T0 \toT1 be the mapping defined as follows: if (x1, x2, . . . , x2n) \inT0 and xk, k > 2, is the twin of x1, then f(x1, x2, . . . , x2n) = (x2, . . . , xk−1, x1, xk, . . . , x2n). The mapping f is injective, but not surjective. Thus F0(n) < F1(n).