21st CanMO 1989 Problem 5 For every permutation a 1 , a 2 , ... , a n of 1, 2, 4, 8, ... , 2 n-1 form the product of all n partial sums a 1 + a 2 + ... + a k . Find the sum of the inverses of all these products. Solution
: 1/2 N , where N = (n-1)n/2. For example, we have: n = 2: 1 2 partial sums 1 3 1/3 2 1 partial sums 2 3 1/6 total 1/2 n = 3: 1 2 4 partial sums 1 3 7 1/21 1 4 2 partial sums 1 5 7 1/35 2 1 4 partial sums 2 3 7 1/42 2 4 1 partial sums 2 6 7 1/84 4 1 2 partial sums 4 5 7 1/140 4 2 1 partial sums 4 6 7 1/168 total 1/8 We claim the more general result that if each a i is a power of 2 with exponent b i , then the sum of the inverses is 2 -B , where B is the sum of the b i . We use induction on n. This is obvious for n = 1. Suppose it is true for < n. Let A be the sum of the a k . The sum of the inverses over the permutations which have a k last is (sum for the n-1 numbers excluding a k ) x 1/A = ( 1/2 to the power of (B - b k ) )/A. Hence the sum of all the inverses is (1/(A 2 B ) x sum of 2 to the power of b k = (1/(A 2 B ) x sum of a k = 1/2 B , which establishes the induction. 21st CanMO 1989 © John Scholes jscholes@kalva.demon.co.uk 29 Aug 2002