26th IMO 1985 shortlist Problem 8 Find 8 positive integers n 1 , n 2 , ... , n 8 such that we can express every integer n with |n| < 1986 as a 1 n 1 + ... + a 8 n 8 with each a i = 0, ±1. Solution
: 1, 3, 3 2 , 3 3 , 3 4 , 3 5 , 3 6 , 3 7 . Solution by Demetres Christofides Put f(n) = 1 + 3 + 3 2 + ... + 3 n . We can prove by induction that any number in the range [-f(n), f(n)] can be represented as a 0 + a 1 3 + ... + a n 3 n with each a i = 0 or ±1. It is evidently true for n = 1. So suppose it is true for n. Note that f(n) = (3 n+1 - 1)/2, so f(n) + 1 - 3 n+1 > - (3 n+1 - 1)/2 = - f(n). So if f(n) < m ≤ f(n+1), then -f(n) < m - 3 n+1 ≤ f(n). By induction m - 3 n+1 = a 0 + ... + a n 3 n , and hence m = a 0 + ... + a n+1 3 n+1 . Similarly for -f(n+1) ≤ m < -f(n), whilst for -f(n) <= m ≤ f(n), the result follows immediately. That completes the induction. [Another way of looking at it is that there are n+1 coefficients each of which can take 3 values, so there are 3 n+1 possibilities. No two possibilities can give the same number, or, equating them and moving negative coefficients to the opposite side, we would have two different representations for the same number in base 3. But obviously all the values lie in the range [-f(n), f(n)], and that range contains just 3 n+1 values.] 26th IMO shortlist 1985 © John Scholes jscholes@kalva.demon.co.uk 11 Sep 2002