23rd CanMO 1991 Problem 2 Find the sum of all positive integers which have n 1s and n 0s when written in base 2.
The first digit must be 1. Then the remaining 2n-1 digits are subject only to the constraint that n are 0 and n-1 are 1. So there are (2n-1)!/(n! (n-1)! ) possibilities. There are (2n-2)!/( ( n! (n-2)! ) with a 1 in any given position (apart from the first). Thus the sum is (2n-1)!/(n! (n-1)! ) 2 2n-1 + (2n-2)!/( n! (n-2)! ) (1 + 2 + 2 2 + ... + 2 2n-2 ) = (2n-1)!/(n! (n-1)! ) 2 2n-1 + (2n-2)!/( n! (n-2)! ) (2 2n-1 - 1). For n = 1 the formula breaks down, but in that case the sum is obviously 2. 23rd CanMO 1991 © John Scholes jscholes@kalva.demon.co.uk 3 Aug 2002