### IMO 1989

Problem 6

A permutation {x1, x2, ... , xm} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |xi - xi+1| = n for at least one i in {1, 2, ... , 2n-1}. Show that for each n there are more permutations with property P than without.

Solution

from Arthur Engel, Problem-Solving Strategies, Springer 1998 [Problem books in mathematics series], ISBN 0387982191. A rather good training book.

Let Ak be the set of permutations with k and k+n in neighboring positions, and let A be the set of permutations with property P, so that A is the union of the Ak.

Then |A| = Sumk |Ak| - Sumk<l |AkÇAl| + Sumk<l<m |AkÇAlÇAm| - ... . But this is an alternating sequence of monotonically decreasing terms, hence |A| >= Sumk |Ak| - Sumk<l |AkÇAl|.

But |Ak| = 2 (2n - 1)! (two orders for k, k+n and then (2n - 1)! ways of arranging the 2n - 1 items, treating k, k+n as a single item). Similarly, |AkÇAl| = 4 (2n - 2)! So |A| >= (2n - 2)! [n.2(2n -1) - n(n - 1)/2 4] = 2n2 (2n - 2)! > (2n)!/2.

The solutions given on this site are not always complete, they are designed to be sufficient for anyone who has thought hard about the problem.

(C) John Scholes
jscholes@kalva.demon.co.uk
3 Sep 1999