29th British Mathematical Olympiad 1993 Problems

29th British Mathematical Olympiad 1993 Problems

1.  The angles in the diagram below are measured in some unknown unit, so that a, b, ... , k, l are all distinct positive integers. Find the smallest possible value of a + b + c and give the corresponding values of a, b, ... , k, l.

2.  p > 3 is prime. m = (4^p - 1)/3. Show that 2^m-1 = 1 mod m.

3.  P is a point inside the triangle ABC. x = ∠BPC - ∠A, y = ∠CPA - ∠B, z = ∠APB - ∠C. Show that PA sin A/sin x = PB sin B/sin y = PC sin C/sin z.

4.  For 0 < m < 10, let S(m, n) is the set of all positive integers with n 1s, n 2s, n 3s, ... , n ms. For a positive integer N let d(N) be the sum of the absolute differences between all pairs of adjacent digits. For example, d(122313) = 1 + 0 + 1 + 2 + 2 = 6. Find the mean value of d(N) for N in S(m, n). 

Solutions

Problem

The angles in the diagram below are measured in some unknown unit, so that a, b, ... , k, l are all distinct positive integers. Find the smallest possible value of a + b + c and give the corresponding values of a, b, ... , k, l. 

Solution

Answer: 20.

We require the angles to satisfy: a + g + h = d + e + f = c + k + l = b + i + j = g + f + i = h + e + l = d + j + k = a + b + c. (One of these equations is dependent on the others.)

So we have to find some integer k which can be partitioned in many different ways as the sum of three distinct integers. Suppose a + b + c + ... + l = n. The smallest possible value of n is 1 + 2 + 3 + ... + 12 = 78 (since the numbers are all distinct). But note that each number occurs twice in the equations above, so 8k = 2n, or n = 4k. So n must be a multiple of 4 and hence its smallest value is 80. Note also that a + b + c = k, so minimising a + b + c is equivalent to minimising n.

If n = 80, the only possibilities are {1, 2, 3, ... , 9, 10, 12, 13} or {1, 2, ... , 10, 11, 14}. At this point it is not obvious how to proceed. A good deal of trial and error produces a = 1, b = 6, c = 13, d = 8, e = 3, f = 9, g = 7, h = 12, i = 4, j = 10, k = 2, l = 5. So there is a solution for k = 20, so 20 is the required minimum. 

Problem 2

p > 3 is prime. m = (4^p - 1)/3. Show that 2^m-1 = 1 mod m.

Solution

By Fermat, So 4^p = 4 mod p, so 3m = 3 mod p. But p > 3 and prime, so m = 1 mod p. Also 4^p - 1 is odd, so m is odd and hence m - 1 is even. So we may write m - 1 = 2kp. Hence 2^m-1 = 4^pk = (3m + 1)^k. Expanding by the binomial theorem, we see that (3m + 1)^k = 1 mod m and hence 2^m-1 = 1 mod m.

 Problem 3

P is a point inside the triangle ABC. x = ∠BPC - ∠A, y = ∠CPA - ∠B, z = ∠APB - ∠C. Show that PA sin A/sin x = PB sin B/sin y = PC sin C/sin z.

Solution

Extend AP, BP, CP to meet the circumcircle again at D, E, F respectively. Consider the triangle PEC. We have ∠PEC = ∠BEC (same angle) = A (E on circumcircle). Also ∠BPC = ∠PEC + ∠ECP, so ∠ECP = x. Hence sin A/sin x = PC/PE. Similarly, sin B/sin y = PA/PF. So we have to show that PA·PC/PE = PB·PA/PF or PC/PE = PB/PF. But CF and BE are chords intersecting at P, so PC·PF = PB·PE.

The other equation follows similarly. 

Problem 4

For 0 < m < 10, let S(m, n) is the set of all positive integers with n 1s, n 2s, n 3s, ... , n ms. For a positive integer N let d(N) be the sum of the absolute differences between all pairs of adjacent digits. For example, d(122313) = 1 + 0 + 1 + 2 + 2 = 6. Find the mean value of d(N) for N in S(m, n).

Solution

Answer: n(m² - 1)/3.

Consider the number of ways of placing two different digits h and k next to each other in positions 1 and 2. The other mn - 2 digits can be permuted in (mn-2)! ways. But there are m-2 groups of n identical digits and 2 groups of n-1 identical digits, so the total number of ways is (mn-2)! / (n!^m-2 (n-1)!²). This is independent of the identity of h and k. There are 2(m-1) pairs h, k with difference 1, 2(m-2) pairs with difference 2, and so on, up to 2 pairs with difference m-1. Thus the total absolute difference between the first two digits (totalled over all members of S(m, n) ) is 2( (m-1)1 + (m-2)2 + ... + 1(m-1) )(mn-2)! /( n!^m-2 (n-1)!²) = f(m, n).

Exactly the same argument applies to the total absolute difference for positions 2 and 3, 3 and 4 and so on up to mn-1 and mn. Thus the total of d(N) over all members of S(m, n) is f(m, n) (mn-1). There are (mn)! / n!^m members of S(m, n), so the mean is f(m, n) (mn-1) n!^m/ (mn)! .

We have (m-1)1 + (m-2)2 + ... + 1(m-1) = (m + 2m + 3m + ... + m.m) - (1² + 2² + ... + m²) = m²(m+1)/2 - m(m+1)(2m+1)/6 = m(m+1)(3m - 2m - 1)/6 = m(m² - 1)/6. Hence the mean is 1/3 m(m² - 1) n!²/( (n-1)!² mn) = n(m² - 1)/3.

It is worth checking this for a few small values. Obviously the mean for S(1, n) = {11...1} is zero, which checks. We have S(2, 1) = {12, 21}, mean 1, which checks. We have S(2, 2) = {1122, 1212, 1221, 2112, 2121, 2211} mean 2, which checks.

As a further check, we found 2(m-1 + m-2 + ... + 1) (mn-2)! / (n!^m-2 (n-1)!²) = m(m-1) (mn-2)! /( n!^m-2 (n-1)!² ) numbers with different digits in positions 1 and 2. There are also m.(mn-2)!/( n!^m-1 (n-2)! ) numbers with the same first digit in positions 1 and 2. So in total we have (mn-2)!/n!^m (m(m-1) n² + m n(n-1) ) = (mn-2)!/n!^m mn ((m-1) n + n-1 ) = (mn)!/n!^m as required.