39th British Mathematical Olympiad 2003 Problems

1.  Find all integers 0 < a < b < c such that b - a = c - b and none of a, b, c have a prime factor greater than 3.

2.  D is a point on the side AB of the triangle ABC such that AB = 4·AD. P is a point on the circumcircle such that angle ADP = angle C. Show that PB = 2·PD.

3.  f is a bijection on the positive integers. Show that there are three positive integers a₀ < a₁ < a₂ in arithmetic progression such that f(a₀) < f(a₁) < f(a₂). Is there necessarily an arithmetic progression a₁ < a₂ < ... < a₂₀₀₃ such that f(a₀) < f(a₁) < ... < f(a₂₀₀₃)?

4.  Let X be the set of non-negative integers and f : X → X a map such that ( f(2n+1) )² - ( f(2n) )² = 6 f(n) + 1 and f(2n) ≥ f(n) for all n in X. How many numbers in f(X) are less than 2003? 

Solutions

Problem 1

Find all integers 0 < a < b < c such that b - a = c - b and none of a, b, c have a prime factor greater than 3.

Answer

(a, b, c) = (k, 2k, 3k), (2k, 3k, 4k) or (2k, 9k, 16k), where k = 2^m3ⁿ.

Solution

It is sufficient to find solutions (A, B, C) without any common factor k which divides A, B and C, for then the complete set of solutions is (kA, kB, kC) with k = 2^m3ⁿ.

Put D = B - A, then C = A + 2D, which has the same parity as A, so A and B must have opposite parity.

Suppose A is odd. Then C is odd and greater than 1, hence a power of 3. If A > 1, then A is also a power of 3, and hence B = (A + C)/2 is also. Contradiction. So A must be 1. Suppose C = 3ⁿ. Then B = (A + C)/2 = (1 + (4 - 1)ⁿ)/2 = (1 + (-1)ⁿ + (-1)^n-14n + terms in 4² and higher)/2. Hence n is odd and B = 2 mod 4. But B is a power of 2, so B = 2 and C = 3.

Suppose A is even, then B is odd and hence a power of 3. If A is divisible by 3, then so is C. Contradiction. So A must be a power of 2. Similarly, C must be a power of 2. If A is divisible by 4, then since C is a larger power of 2, it must also be divisible by 4. Hence 2D = C - A is divisible by 4, so B is divisible by 2. Contradiction. So A must be 2. It is easy to check that (A, B, C) = (2, 3, 4) and (2, 9, 16) are solutions. It remains to show that there are no solutions with B divisible by 27.

Thanks to John Pye for the next part

Suppose there is such a solution, then we have A = 2, C a power of 2, B = 3ⁿ = 2^m - 1 ( (A+C)/2). B = 27 does not work, so B ≥ 81 and hence m ≥ 4. We have 3⁴ = 1 mod 16, so it is easy to check that 3^4k - 1 = 0 mod 16, 3^4k+1 - 1 = 2 mod 16, 3^4k+2 - 1 = 8 mod 16, 3^4k+3 - 1 = 10 mod 16. So n must be a multiple of 4. But since 3⁴ = 1 mod 5, that means 3ⁿ - 1 = 0 mod 5, so B cannot be a power of 2. Contradiction. 

Problem 2

D is a point on the side AB of the triangle ABC such that AB = 4·AD. P is a point on the circumcircle such that angle ADP = angle C. Show that PB = 2·PD.

Solution

 

Note that angle APB = angle C, so triangles BAP, PAD are similar. Hence BA/AP = PA/AD, giving PA = 2AD. Also BP/AP = PD/AD, so PB/PD = AP/AD = 2, as required. 

Problem 3

f is a bijection on the positive integers. Show that there are three positive integers a₀ < a₁ < a₂ in arithmetic progression such that f(a₀) < f(a₁) < f(a₂). Is there necessarily an arithmetic progression a₁ < a₂ < ... < a₂₀₀₃ such that f(a₀) < f(a₁) < ... < f(a₂₀₀₃)?

Solution

Thanks to Arne Smeets

Suppose f(k) = 1. Then certainly f(k) < f(k + h) for any positive integer h. Now consider the sequence f(k+1), f(k+2), f(k+4), f(k+8), f(k+16), ... . Each term is different since k is a bijection. It cannot be always decreasing, since there are only finitely many positive values less than f(k+1). So for some 2ⁿ we have f(k + 2ⁿ) < f(k + 2ⁿ⁺¹). But now k, k + 2ⁿ, k + 2ⁿ⁺¹ is the required arithmetic progression.

We can find a bijection which does not even give f(a₀) < f(a₁) < f(a₂) < f(a₃) for any arithmetic progression a₀ < a₁ < a₂ < a₃.

For example, take f(n) = 2, 1, 8, 7, ... , 3, 26, 25, ... , 9, 80, 79, ... , 27, ... (for n = 1, 2, 3, ... ). Suppose that f(a₀) < f(a₁) < f(a₂) < f(a₃). Now a₁ and a₂ cannot be in the same block, and a₂ and a₃ cannot be in the same block, so there must be a complete block between a₁ and a₃. In other words, if 3ⁿ <= a₁ < 3ⁿ⁺¹, then a₃ >= 3ⁿ⁺² and a₃ - a₁ > 2·3ⁿ⁺¹. But a₁ - a₀ < 3ⁿ⁺¹. So a₀, a₁, a₂, a₃ is not an arithmetic progression. 

Problem 4

Let X be the set of non-negative integers and f : X → X a map such that ( f(2n+1) )² - ( f(2n) )² = 6 f(n) + 1 and f(2n) >= f(n) for all n in X. How many numbers in f(X) are less than 2003?

Answer

128

Solution

Obviously f(2n) + 3 > f(2n+1) > f(2n), so f(2n+1) = f(2n) + 1 or f(2n) + 2. But f(2n)² + 6 f(n) + 1 and f(2n)² have opposite parity, so we must have f(2n+1) = f(2n) + 1. Hence f(2n) = 3 f(n).

So, in particular, f(0) = 0. Hence f(1) = 1. A trivial induction now gives that f is strictly monotonic increasing. Obviously f(128) = 3⁷ = 2187 > 2003.

f(127) = f(126) + 1 = 3 f(63) + 1 = 3 f(62) + 4 = 9 f(31) + 4 = 9 f(30) + 13 = 27 f(15) + 13 = 27 f(14) + 40 = 81 f(7) + 40 = 81 f(6) + 121 = 243 f(3) + 121 = 243 f(2) + 364 = 729 f(1) + 364 = 1093 < 2003. So the 128 distinct numbers f(0), f(1), ... , f(127) are less than 2003.