IMO shortlist 1985/19 solution

26th IMO 1985 shortlist

Problem 19

Show that the sequence [n √2] for n = 1, 2, 3, ... contains infinitely many powers of 2.

Solution

Solution by Demetres Christofides

Suppose not, so that the highest power of 2 in the sequence is 2^m-1. Since √2 < 2, the difference between [n√2] and [(n+1)√2] is at most 2. Since √2 > 1, the difference is at least 1. So it is either 1 or 2. So for some N we must have [N√2] = 2^m - 1, [(N+1)√2] = 2^m + 1.

We claim that for k = 0, 1, 2, ... we have [2^kN√2] = 2^m+k - 1, [(2^kN+1)√2] = 2^m+k + 1. We use induction on k. It is true for k = 0. So suppose it is true for k. Then 2^kN√2 < 2^m+k, so 2^k+1N√2 < 2^m+k+1. Also (2^kN+1)√2 > 2^m+k + 1, so 2^kN√2 > 2^m+k - (√2 - 1) and hence 2^k+1N√2 > 2^m+k+1 - 2(√2 - 1) > 2^m+k+1 - 1. Hence [2^k+1N√2] = 2^m+k+1 - 1. So [(2^k+1N+1)√2] = 2^m+k+1 or 2^m+k+1 + 1. By assumption it is not 2^m+k+1, so it must be 2^m+k+1 + 1. That establishes the result for k+1 and hence for all k.

But √2 is irrational, so N√2 = 2^m - h for some positive real h. Take k such that h > 1/2^k, then 2^kN√2 = 2^m+k - h2^k < 2^m+k - 1, so [2^kN√2] < 2^m+k - 1. Contradiction. So the assumption must be wrong and there must be infinitiely many powers of 2.

26th IMO shortlist 1985