37th British Mathematical Olympiad 2001 Problems

37th British Mathematical Olympiad 2001 Problems

1.  A has a marbles and B has b < a marbles. Starting with A each gives the other enough marbles to double the number he has. After 2n such transfers A has b marbles. Find a/b in terms of n.

2.  Find all integer solutions to m²n + 1 = m² + 2mn + 2m + n.

3.  ABC is a triangle with AB greater than AC. AD is the angle bisector. E is the point on AB such that ED is perpendicular to BC. F is the point on AC such that DE bisects angle BEF. Show that ∠FDC = ∠BAD.

4.  n dwarfs with heights 1, 2, 3, ... , n stand in a circle. S is the sum of the (non-negative) differences between each adjacent pair of dwarfs. What are the maximum and minimum possible values of S? 

Solutions

Problem 1

A has a marbles and B has b < a marbles. Starting with A each gives the other enough marbles to double the number he has. After 2n such transfers A has b marbles. Find a/b in terms of n.

Solution

After 2 transfers A has 2(a - b) = 4a - 2N marbles, where N = a + b. Suppose A has a_n marbles after 2n transfers. We have just shown that a_n+1 = 4a_n - 2N. Put c_n = a_n - 2N/3, then c_n+1 = 4c_n. We have c₀ = a - 2N/3, so c_n = 4ⁿa - 4ⁿ2N/3. Hence a_n = 4ⁿa - 4ⁿ2N/3 + 2N/3 = (4ⁿ + 2)a/3 - 2(4ⁿ - 1)b/3. We require a_n = b and hence a/b = (2.4ⁿ + 1)/(4ⁿ + 2).

Note that we have not so far proved that there is a solution for n. We have just showed that if there is a solution then a/b has that ratio. It might be that one person has a negative number of marbles at some point. Fortunately, we do not have to worry whether the question requires us to show that n is possible, because it is easy to show that it is. The key observation is that if one person goes negative, then they remain negative. But after 2n moves neither A nor B is negative, so they cannot have been negative at any intermediate stage. 

Problem 2

Find all integer solutions to m²n + 1 = m² + 2mn + 2m + n.

Solution

Answer: (m, n) = (-1, -1), (0, 1), (1, -1), (2, -7), or (3, 7).

We have m²(n - 1) = 2m(n + 1) + n - 1 = 2m(n - 1) + 4m + (n - 1). Put k = n - 1 and this becomes m²k = 2mk + 4m + k (*).

If k = 0, then m = 0. This gives the solution m = 0, n = 1. If m = 0, then k = 0, so we assume m and k are non-zero. From (*) m must divide k and k must divide 4m. Put k = mh. Then h divides 4, so h = ±1, ±2 or ±4. Also we can write (*) as (m² - 2m - 1)h - 4 = 0.

If h = 1, then m² - 2m - 5 = 0, which has no integral solutions. If h = -1, then m² - 2m + 3 = 0, which has no integral solutions. If h = 2, then m² - 2m - 3 = 0, which has solutions m = -1 or 3. If h = -2, then m² - 2m + 1 = 0, so m = 1. If h = 4, then m² - 2m - 2 = 0, which has no integral solutions. If h = -4, then m² - 2m = 0, which has solutions m = 0, 2. 

Problem 3

ABC is a triangle with AB greater than AC. AD is the angle bisector. E is the point on AB such that ED is perpendicular to BC. F is the point on AC such that DE bisects ∠BEF. Show that ∠FDC = ∠BAD.

Solution

CD bisects ∠A and DE is the external bisector of ∠FEA. Hence D is an excenter of AEF and DF is an external bisector of ∠AFE.

∠BED = 90^o - ∠B, so ∠AEF = 2 ∠B, so ∠AFE = ∠C - ∠B. Hence ∠CFD = (180^o - (∠C - ∠B))/2 = 90^o - ∠C/2 + ∠B/2. Hence ∠FDC = 180^o - (90^o - ∠C/2 + ∠B/2) - C = 90^o - ∠B/2 - ∠C/2 = ∠A/2 = ∠BAD. 

Problem 4

n dwarfs with heights 1, 2, 3, ... , n stand in a circle. S is the sum of the (non-negative) differences between each adjacent pair of dwarfs. What are the maximum and minimum possible values of S?

Solution

Answer: min 2n - 2, max [n²/2].

The minimum is obviously 2(n-1). The difference between 1 and n is n-1 and the sum of the signed differences as we go from n to 1 either way round the circle must be n-1. The sum of the unsigned differences must be at least as large, so S ≥ 2(n-1). This is achieved by the order 1, 2, 3, ... , n.

The maximum is almost obvious. If the numbers are a₁, a₂, ... , a_n. Then each difference is a_i+1 - a_i or - a_i+1 + a_i. So the total of all the differences is k₁a₁ + k₂a₂ + ... + k_na_n, where each k_i is -2, 0 or 2 and their sum is 0. So permuting back to 1, 2, ... , n the sum is h₁ + 2h₂ + 3h₃ + ... + nh_n, where each h_i is 0 or ±2 and the sum of the h_i is 0. If n = 2m, this is maximised by taking h₁ = h₂ = ... = h_m = -2 and h_m+1 = ... = h_2m = 2, giving a sum of 2m². If n = 2m+1, it is maximised by taking h₁ = ... = h_m = -2, h_m+1 = 0, h_m+2 = ... = h_2m+1 = 2, giving a sum of 2m(m+1).

Checking that this can be achieved, we take: 1, 2m, 2, 2m-1, 3, 2m-2, ... , m-1, m+2, m, m+1 in the even case and 1, 2m+1, 2, 2m-1, 3, 2m-3, ... , m-1, m+3, m, m+2, m+1 in the odd case.