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| ≥ ∑k |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.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
3 Sep 1999