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 |AkAl| + Sumk<l<m |AkAlAm| - ... . But this is an alternating sequence of monotonically decreasing terms, hence |A| >= Sumk |Ak| - Sumk<l |AkAl|.

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, |AkAl| = 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.

 

30th IMO 1989

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