15th Chinese 2000 Problem B1 Let S be the set of all permutations (a 1 , a 2 , ... , a n ) of (1, 2, ... , n) which have just one element a i (apart from a 1 ) which is greater than all its predecessors. Find the mean of a 1 over all elements of S. Solution
: Let the mean be f(n) and let s n = 1 + 1/2 + ... + 1/n. Then f(n) = n - (n-1)/s n-1 . Solution by Carl Johan Ragnarsson Let a(n) be the number of permutations in S and b(n) the sum of their first elements, so that f(n) = a(n)/b(n). We find that a(1) = 0, a(2) = 1, b(2) = 1, a(3) = 3, b(3) = 5. If the first element of the permutation is 1, then whatever element comes second will be greater than all its predecessors. But n will also be greater than all its predecessors, wherever it comes. So n must come second. But then the order is immaterial, because nothing exceeds n. Thus there are exactly (n-2)! permutations with first element 1 in S. If the first element is not 1, then 1 can come anywhere and the other numbers form can all be decremented by 1 to give a permutation of n-1 which meets the conditions. Conversely, given a permutation of n-1 which meets the conditions we can increase each element by 1 and then put 1 in any of the n-1 positions except the first to get a permutation for n which meets the conditions. Thus a(n) = (n-1) a(n-1) + (n-2)! and b(n) = (n-1) (a(n-1) + b(n-1) ) + (n-2)! = a(n) + (n-1) b(n-1). It is now a trivial induction to show that a(n) = (n-1)! s n-1 . It is also easy to show by induction that b(n) = n! s n-1 - (n-1).(n-1)! . For n = 2 this reads b(2) = 2 - 1 = 1, which is true. Assuming it is true for n-1, we have b n = a(n) + (n-1) b(n-1) = (n-1)! s n-1 + (n-1) (n-1)! s n-2 - (n-1)(n-2).(n-2)! = (n-1)! s n-2 + (n-2)! + (n-1) (n-1)! s n-2 - (n-1)(n-2).(n-2)! = n! s n-2 + (n-2)! - (n-2).(n-1)! = n! s n-1 - (n-1).(n-1)! - n!/(n-1) + (n-2)! + (n-1)! = n! s n-1 - (n-1).(n-1)! + (n-2)! (-n + 1 + n - 1) = n! s n-1 - (n-1).(n-1)! which completes the induction. The answer n - (n-1)/s n is now immediate. 15th Chinese 2000 (C) John Scholes jscholes@kalva.demon.co.uk 22 July 2002