33rd British Mathematical Olympiad 1997 Problems

33rd British Mathematical Olympiad 1997 Problems

1.  M and N are 9-digit numbers. If any digit of M is replaced by the corresponding digit of N (eg the 10s digit of M replaced by the 10s digit of N), then the resulting integer is a multiple of 7. Show that if any digit of N is replaced by the corresponding digit of M, then the resulting integer must be a multiple of 7. Find d > 9, such that the result remains true when M and N are d-digit numbers.

2.  ABC is an acute-angled triangle. The median BM and the altitude CF have equal length, and ∠MBC = ∠FCA. Show that ABC must be equilateral.

3.  Find the number of polynomials of degree 5 with distinct coefficients from the set {1, 2, ... , 9} which are divisible by x² - x + 1.

4.  Let S be the set {1/1, 1/2, 1/3, 1/4, ... }. The subset {1/20, 1/8, 1/5} is an arithmetic progression of length 3 and is maximal, because it cannot be extended (within S) to a longer arithmetic progression. Find a maximal arithmetic progression in S of length 1996. Is there a maximal arithmetic progression in S of length 1997?

Problem 1

M and N are 9-digit numbers. If any digit of M is replaced by the corresponding digit of N (eg the 10s digit of M replaced by the 10s digit of N), then the resulting integer is a multiple of 7. Show that if any digit of N is replaced by the corresponding digit of M, then the resulting integer must be a multiple of 7. Find d > 9, such that the result remains true when M and N are d-digit numbers.

Solution

Let M = m₈10⁸ + m₇10⁷ + ... + m₀ and N = n₈10⁸ + ... + n₀. We have:
n₈10⁸ + m₇10⁷ + m₆10⁶ + ... + m₁10 + m₀ = 0 mod 7
m₈10⁸ + n₇10⁷ + m₆10⁶ + ... + m₁10 + m₀ = 0 mod 7
m₈10⁸ + m₇10⁷ + n₆10⁶ + ... + m₁10 + m₀ = 0 mod 7
...
m₈10⁸ + m₇10⁷ + m₆10⁶ + ... + n₁10 + m₀ = 0 mod 7
m₈10⁸ + m₇10⁷ + m₆10⁶ + ... + m₁10 + n₀ = 0 mod 7

Adding all but the first equation we get:
8m₈10⁸ + (n₇ + 7m₇) 10⁷ + (n₆ + 7m₆) 10⁶ + ... + (n₀ + 7m₀) = 0 mod 7. Hence
m₈10⁸ + n₇10⁷ + n₆10⁶ + ... + n₀ = 0 mod 7, which shows that substituting the first digit from M into N gives a number divisible by 7.

Similarly, adding all but the second equation, we find that substituting the second digit from M into N gives a number divisible by 7, and so on.

Obviously the same argument works for any d = 2 mod 7. 

Problem 2

ABC is an acute-angled triangle. The median BM and the altitude CF have equal length, and ∠MBC = ∠FCA. Show that ABC must be equilateral.

Solution

Solution by Paul Smith

Put ∠MBC = ∠FCA = x. Since M is the midpoint of AC and ∠AFC = 90^o, M must be the center of the circle through A, F, C, so MF = MC = MA. Put MF = k. Then CF = 2k cos x.

But ∠MBC = ∠FCA = ∠FCM = ∠MFC, so MFBC is cyclic. Hence ∠BMC = ∠CFB = 90^o. So BM/k = cot MBC = cot x. But CF = BM, so sin x = 1/2. Hence x = 30^o. Hence ∠C = 60^o. Also ∠A = 90^o - angle FCA = 60^o. So the triangle is equilateral.

I originally had this appalling slog:

Let the side lengths be BC = a, CA = b, AB = C and let CF = BM = m. Let ∠MBC = ∠FCA = x. By the cosine formula we have: c² = m² + b²/4 - mb cos BMA, a² = m² + b²/4 + mb cos BMA. Adding, m² = a²/2 + c²/2 - b²/4 (1).

From triangle FCA, m = b cos x. By the cosine formula to MBC, b²/4 = m² + a² - 2am cos x. Hence b²/4 = m² + a² - 2am²b = (b - 2a)m²/b + a². Hence b = 2a or m² = b(b + 2a)/4.

Suppose b = 2a. If m <= a, then B lies inside or on the circle center M radius MA and hence ∠ABC ≥ 90^o. But we are told the triangle is acute-angled, so ∠ABC < 90^o. Hence m > a. But CF ≤ CB = a. Contradiction. So we cannot have b = 2a.

Hence m²= b(b + 2a)/4, so from (1), 2a² + 2c² - b² = b² + 2ab or b² = a² + c² - ab.

Let k be the area of ABC. By Heron's formula we have that 16k² = (a + b + c)(a + b - c)(a - b + c)(-a + b + c) = - a⁴ - b⁴ - c⁴ + 2a²b² + 2b²c² + 2c²a². But 16k² is also 4m²c² = c²b(b + 2a). So we have -a⁴ - b⁴ + 2a²b² + c²(2a² - 2ab + b²) - c⁴ = 0. Substituting for c² ( = b² - a² + ab) we get: 0 = -4a⁴ - b⁴ + 2a²b² - 3b³a + 6a³b = (a - b)(2a + b)(2a² - 2ab - b²).

Clearly 2a + b is non-zero. If 2a² - 2ab - b² = 0, then 3a² = (a + b)², so b = (√3 - 1)a. Then substituting in the previous relation for c, we get c = b/√2. So we have for some k, a = (1 + √3)k, b = 2k, c = (√2)k. But then a² > b² + c², so the triangle is not acute-angled. So we must have a = b. Then using the previous relation for c, we get c = a also. 

Problem 3

Find the number of polynomials of degree 5 with distinct coefficients from the set {1, 2, ... , 9} which are divisible by x² - x + 1.

Solution

Answer: 624.

This seems to be a laborious exercise in counting. Suppose that the polynomial is (x² - x + 1)(ax³ + bx² + cx + d). Multiplying out, we find that the coefficients are: a, b-a, c-(b-a), b-(c-d), c-d, d. Put e = b-a, f = c-d. Then the coefficients are: a, e, d+f-e, a+e-f, f, d. Put k = e-f. Then the coefficients are: a, f+k, d-k, a+k, f, d. Suppose k > 0. Put g = d-k. then the coefficients are (rearranging the order) a, f, g, a+k, f+k, g+k. Similarly, if k < 0, put h = -k, and the coefficients are a, e, d+h, a-h, e+h, d. Putting g = a-h and rearranging the order we get: d, e, g, d+h, e+h, g+h. The two types (k positive and negative) obviously do not overlap and there are evidently equal numbers of each. So we have to find the number of sets a, f, g, a+k, f+k, g+k. By symmetry, the number of sets must be 6 times the number with a < f < g. However, I cannot see an elegant way to count the number with a < f < g. Simply listing them gives 52 possibilities.

if k = 1, a = 1, f = 3, then g can be 5, 6, 7, or 8.  

if k = 1, a = 1, f = 4, then g can be 6, 7 or 8

if k = 1, a = 1, f = 5, then g can be 7 or 8

if k = 1, a = 1, f = 6, then g must be 8

if k = 1, a = 2, f = 4, then g can be 6, 7 or 8

if k = 1, a = 2, f = 5, then g can be 7 or 8

if k = 1, a = 2, f = 6, then g must be 8

if k = 1, a = 3, f = 5, then g can be 7 or 8

if k = 1, a = 3, f = 6, then g must be 8

if k = 2, a = 1, f = 2, then g can be 5, 6 or 7

if k = 2, a = 1, f = 4, then g can be 5 or 7

if k = 2, a = 1, f = 5, then g must be 6

if k = 2, a = 1, f = 6, then g must be 7

if k = 2, a = 2, f = 3, then g can be 6 or 7

if k = 2, a = 2, f = 5, then g must be 6

if k = 2, a = 2, f = 6, then g must be 7

if k = 2, a = 3, f = 4, then g must be 7

if k = 2, a = 3, f = 6, then g must be 7

if k = 3, a = 1, f = 2, then g can be 3 or 6

if k = 3, a = 1, f = 3, then g must be 5

if k = 3, a = 1, f = 5, then g must be 6

if k = 3, a = 2, f = 3, then g must be 4

if k = 3, a = 2, f = 4, then g must be 6

if k = 3, a = 3, f = 4, then g must be 5

if k = 3, a = 4, f = 5, then g must be 6

if k = 4, a = 1, f = 2, then g can be 3 or 4

if k = 4, a = 1, f = 3, then g must be 4

if k = 4, a = 2, f = 3, then g can be 4 or 5

if k = 4, a = 2, f = 4, then g must be 5

if k = 5, a = 1, f = 2, then g must be 3 or 4

if k = 5, a = 1, f = 3, then g must be 4

if k = 5, a = 2, f = 3, then g must be 4

if k = 6, a = 1, f = 2, then g must be 3

Comment: can anyone come up with a better solution!

Problem 4

Let S be the set {1/1, 1/2, 1/3, 1/4, ... }. The subset {1/20, 1/8, 1/5} is an arithmetic progression of length 3 and is maximal, because it cannot be extended (within S) to a longer arithmetic progression. Find a maximal arithmetic progression in S of length 1996. Is there a maximal arithmetic progression in S of length 1997?

Solution

Let k = 1/1993! . Then h divides k for h = 1, 2, ... , 1996, but not for 1997, which is prime. Hence 1/k, 2/k, 3/k, ... , 1996/k is a maximal arithmetic progression in S of length 1996 (extending it would require 0 or 1997/1993! to be in S, which they are not).

6.1998 - 1 = 11987 is prime. So put k = 11986! and consider the progression 5/k, 11/k, 17/k, ... , 11981/k. It has 1997 terms in S. It cannot be extended, because -1/k and 11987/k are not in S.

[This conceals some work, because we have to try 2·1998 - 1 (factor 5), 3·1998 - 1 (factor 13), 3·1998 - 2 (factor 2), 4·1998 - 1 (factor 61), 4·1998 - 2 (factor 2), 4·1998 - 3 (factor 3), 5·1998 - 1 (factor 7), 5·1998 - 2 (factor 2), 5·1998 - 3 (factor 3), 5·1998 - 4 (factor 2), before hitting on 6·1998 - 1 (and checking that requires checking divisibility by about 25 primes).]