IMO shortlist 1985/8 solution

26th IMO 1985 shortlist

Problem 8

Find 8 positive integers n₁, n₂, ... , n₈ such that we can express every integer n with |n| < 1986 as a₁n₁ + ... + a₈n₈ with each a_i = 0, ±1.

Solution

Answer: 1, 3, 3², 3³, 3⁴, 3⁵, 3⁶, 3⁷.

Solution by Demetres Christofides

Put f(n) = 1 + 3 + 3² + ... + 3ⁿ. We can prove by induction that any number in the range [-f(n), f(n)] can be represented as a₀ + a₁3 + ... + a_n3ⁿ 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ⁿ⁺¹ - 1)/2, so f(n) + 1 - 3ⁿ⁺¹ > - (3ⁿ⁺¹ - 1)/2 = - f(n). So if f(n) < m ≤ f(n+1), then -f(n) < m - 3ⁿ⁺¹ ≤ f(n). By induction m - 3ⁿ⁺¹ = a₀ + ... + a_n3ⁿ, and hence m = a₀ + ... + a_n+13ⁿ⁺¹. 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ⁿ⁺¹ 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ⁿ⁺¹ values.]

26th IMO shortlist 1985