19th British Mathematical Olympiad 1983 Problems

19th British Mathematical Olympiad 1983 Problems - Further International Selection Test

1.  Given points A and B and a line l, find the point P which minimises PA² + PB² + PN², where N is the foot of the perpendicular from P to l. State without proof a generalisation to three points.

2.  Each pair of excircles of the triangle ABC has a common tangent which does not contain a side of the triangle. Show that one such tangent is perpendicular to OA, where O is the circumcenter of ABC.

3.  l, m, and n are three lines in space such that neither l nor m is perpendicular to n. Variable points P on l and Q on m are such that PQ is perpendicular to n, The plane through P perpendicular to m meets n at R, and the plane through Q perpendicular to l meets n at S. Show that RS has constant length.

4.  Show that for any positive reals a, b, c, d, e, f we have ab/(a + b) + cd/(c + d) + ef/(e + f) ≤ (a + c + e)(b + d + f)/(a + b + c + d + e + f).

5.  How many permutations a, b, c, d, e, f, g, h of 1, 2, 3, 4, 5, 6, 7, 8 satisfy a < b, b > c, c < d, d> e, e < f, f > g, g < h?

6.  Find all positive integer solutions to (n + 1)^m = n! + 1.

7.  Show that in a colony of mn + 1 mice, either there is a set of m + 1 mice, none of which is a parent of another, or there is an ordered set of n + 1 mice (M₀, M₁, M₂, ... , M_n) such that M_i is the parent of M_i-1 for i = 1, 2, ... , n. 

Problem 1

Given points A and B and a line l, find the point P which minimises PA² + PB² + PN², where N is the foot of the perpendicular from P to l. State without proof a generalisation to three points.

Solution

 

Let M be the midpoint of AB. We have the familiar result that PA² + PB² = 2PM² + 2MA². Hence P must minimise 2PM² + PN² and hence lie on MC, the perpendicular from M to the line. Let G be the point on the segment MC such that GC = 2MG. Suppose P is a distance x from G, taking positive distances towards C. Then PC² + 2PM² = (GC-x)² + 2(GM+x)² = GC² + 2GM² + 2x(2GM-GC) + 2x² = GC² + 2GM² + 2x², which is minimised by taking x = 0. So we should take P at G.

For 3 points and a line, take D to be the centroid of the three points and D' to be the foot of the perpendicular from D to the line. Then P should be taken at the centroid of the three points and D'. 

Problem 2

Each pair of excircles of the triangle ABC has a common tangent which does not contain a side of the triangle. Show that one such tangent is perpendicular to OA, where O is the circumcenter of ABC.

Solution

 

Let the common tangent meet the lines AC, AB at B', C' respectively, and let the line AO meet the line B'C' at Z. Then B' and C' are the reflections of B, C in the line EF, so ∠AB'C' = ∠B. But ∠ZAB' = ∠OAC = 90^o - ∠B (because ∠AOC = 2∠B). Hence ∠AZB' = 90^o. 

Problem 3

l, m, and n are three lines in space such that neither l nor m is perpendicular to n. Variable points P on l and Q on m are such that PQ is perpendicular to n, The plane through P perpendicular to m meets n at R, and the plane through Q perpendicular to l meets n at S. Show that RS has constant length.

Solution

Use vectors. Take any origin O. Take vectors λ, μ, ν parallel to l, m, n. Take fixed points A, B, C on l, m, n. Write the vectors OA, OB, OC as a, b, c. Then OP is a + hλ, OQ is b + kμ. Since PQ is perpendicular to n, we have (a - b + hλ - kμ).ν = 0 (*). Take R to have vector c + rν. Since PR is perpendicular to m, we have (c - a + rν - hλ).μ = 0, so (ν.μ)r = a.μ + hλ.μ - c.μ. Similarly, take S to have vector c + sν. Since QS is perpendicular to l, we have (c - b + sν - kμ).λ = 0, so (ν.λ)s = b.λ + kμ.λ - c.λ. Hence (ν.μ)(ν.λ)(r - s) = (ν.μ)(c-b).λ + (&lambda.μ)(b-a).ν + (&nu.λ)(a-c).μ, where we have used (*) to combine the h and k terms. Thus the distance RS is independent of h, k. 

Problem 4

Show that for any positive reals a, b, c, d, e, f we have ab/(a + b) + cd/(c + d) + ef/(e + f) ≤ (a + c + e)(b + d + f)/(a + b + c + d + e + f).

Solution

With some work (28 terms cancel) multiplying across reduces ab/(a+b) + cd/(c+d) ≤ (a+c)(b+d)/(a+b+c+d) to (ad-bc)² ≥ 0, which is obviously true. The trick is now to apply this again: (a+c)(b+d)/(a+b+c+d) + ef/(e+f) ≤ (a+c+e)(b+d+f)/(a+b+c+d+e+f). 

Problem 5

How many permutations a, b, c, d, e, f, g, h of 1, 2, 3, 4, 5, 6, 7, 8 satisfy a < b, b > c, c < d, d> e, e < f, f > g, g < h?

Answer

1385

Solution

We use the principle of inclusion and exclusion to simplify the counting. Let S be the set of permutations with a < b, c < d, e < f, g < h. Evidently S has 8!/2⁴ = 2520 members. Let A₁ be the subset with b < c, A₂ the subset with d < e, A₃ the subset with f < g. Let A₁₂ be the subset with a < b and d < e, A₁₃ the subset with a < b and f < g, A₂₃ the subset with d < e and f < g, and A₁₂₃ the subset with a < b and d < e and f < g.

Members of A₁ satisfy a < b < c < d and e < f and g < h. We can choose a,b,c,d in 8C4 ways, then d,e in 6 ways. That determines the permutation, so A₁ has 420 members. Similarly, A₂ and A₃ have 420 members. Members of A₁₂ satisfy a < b < c < d < e < f and g < h. We can choose g and h in 8C2 = 28 ways and the permutation is then determined, so A₁₂ has 28 members. Similarly, A₂₃. Members of A₁₃ satisfy a < b < c < d and e < f < g < h. We can choose a, b, c, d in 8C4 = 70 ways and the permutation is then determined, so A₁₃ has 70 members. A₁₂₃ obviously has just one member. Hence the number of elements satisfying the conditions in the question is |S| - |A₁| - |A₂| - |A₃| + |A₁₂| + |A₁₃| + |A₂₃| - |A₁₂₃| = 2520 - 3·420 + 2·28 + 70 - 1 = 1385. 

Problem 6

Find all positive integer solutions to (n + 1)^m = n! + 1.

Answer

(n,m) = (1,1), (2,1), (4,2)

Solution

If n = 1, then m must be 1, which gives a solution. So assume n > 1. Hence n! is even and n! + 1 is odd, so n must be even. If n = 2, then m must be 1 and we have a solution. If n = 4, then 5^m = 25, so m must be 2 which is a solution. So assume n > 4. Then 2, n/2 and n are separate terms of n!, so n² divides n! and hence also (n+1)^m - 1. Expanding by the binomial theorem, we see that n must divide m. Hence, in particular m ≥ n. But now (n+1)^m ≥ (n+1)ⁿ > n! + 1. So there are no solutions for n > 4. 

Problem 7

Show that in a colony of mn + 1 mice, either there is a set of m + 1 mice, none of which is a parent of another, or there is an ordered set of n + 1 mice (M₀, M₁, M₂, ... , M_n) such that M_i is the parent of M_i-1 for i = 1, 2, ... , n.

Solution

This is just a variant of the well-known Erdös-Szekeres result. For each mouse m_i let t_i be the length of the longest parent sequence starting at m_i, where n₁, n₂, ... is a parent sequence if n_j is the parent of n_j-1 for each j. If any t_i ≥ n+1, then we are done. So assume all t_i ≤ n. So there must be at least m+1 mice with the same t_i. Now suppose one of these M was the parent of another M'. Then we could get a parent sequence of length t_i+1 for M' by taking M' followed by M and its parent sequence. That contradicts the maximality of t_i. So none of the m+1 mice is the parent of another.