IMO 1968 Problem B3 For every natural number n evaluate the sum [(n+1)/2] + [(n+2)/4] + [(n+4)/8] + ... + [(n+2 k )/2 k+1 ] + ... , where [x] denotes the greatest integer ≤ x.
For any real x we have [x] = [x/2] + [(x+1]/2]. For if x = 2n + 1 + k, where n is an integer and 0 ≤ k < 1, then lhs = 2n + 1, and rhs = n + n + 1. Similarly, if x = 2n + k. Hence for any integer n, we have: [n/2 k ] - [n/2 k+1 ] = [(n/2 k + 1)/2] = [(n + 2 k )/2 k+1 ]. Hence summing over k, and using the fact that n < 2 k for sufficiently large k, so that [n/2 k ] = 0, we have: n = [(n + 1)/2] + [(n + 2)/4] + [(n + 4)/8] + ... . s are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48- X. 10th IMO 1968 © John Scholes jscholes@kalva.demon.co.uk 3 Oct 1998 Last corrected/updated 3 Oct 1998