15th International Mathematical Olympiad 1973 Problems & Solutions

A1.  OP₁, OP₂, ... , OP_2n+1 are unit vectors in a plane. P₁, P₂, ... , P_2n+1 all lie on the same side of a line through O. Prove that |OP₁ + ... + OP_2n+1| ≥ 1.

A2.  Can we find a finite set of non-coplanar points, such that given any two points, A and B, there are two others, C and D, with the lines AB and CD parallel and distinct?

A3.  a and b are real numbers for which the equation x⁴ + ax³ + bx² + ax + 1 = 0 has at least one real solution. Find the least possible value of a² + b².

B1.  A soldier needs to sweep a region with the shape of an equilateral triangle for mines. The detector has an effective radius equal to half the altitude of the triangle. He starts at a vertex of the triangle. What path should he follow in order to travel the least distance and still sweep the whole region?

B2.  G is a set of non-constant functions f. Each f is defined on the real line and has the form f(x) = ax + b for some real a, b. If f and g are in G, then so is fg, where fg is defined by fg(x) = f(g(x)). If f is in G, then so is the inverse f^-1. If f(x) = ax + b, then f^-1(x) = x/a - b/a. Every f in G has a fixed point (in other words we can find x_f such that f(x_f) = x_f. Prove that all the functions in G have a common fixed point.

B3.  a₁, a₂, ... , a_n are positive reals, and q satisfies 0 < q < 1. Find b₁, b₂, ... , b_n such that: (a)  a_i < b_i for i = 1, 2, ... , n,

(b)  q < b_i+1/b_i < 1/q for i = 1, 2, ... , n-1,

(c)  b₁ + b₂ + ... + b_n < (a₁ + a₂ + ... + a_n)(1 + q)/(1 - q). 

Solutions

Problem A1

OP₁, OP₂, ... , OP_2n+1 are unit vectors in a plane. P₁, P₂, ... , P_2n+1 all lie on the same side of a line through O. Prove that |OP₁ + ... + OP_2n+1| ≥ 1.

Solution

We proceed by induction on n. It is clearly true for n = 1. Assume it is true for 2n-1. Given OP_i for 2n+1, reorder them so that all OP_i lie between OP_2n and OP_2n+1. Then u = OP_2n + OP_2n+1 lies along the angle bisector of angle P_2nOP_2n+1 and hence makes an angle less than 90^o with v = OP₁ + OP₂ + ... + OP_2n-1 (which must lie between OP₁ and OP_2n-1 and hence between OP_2n and OP_2n+1. By induction |v| ≥ 1. But |u + v| ≥ |v| (use the cosine formula). Hence the result is true for 2n+1.

It is clearly best possible: take OP₁ = ... = OP_n = -OP_n+1 = ... = -OP_2n, and OP_2n+1 in an arbitrary direction. 

Problem A2

Can we find a finite set of non-coplanar points, such that given any two points, A and B, there are two others, C and D, with the lines AB and CD parallel and distinct?

Solution

To warm up, we may notice that a regular hexagon is a planar set satisfying the condition.

Take two regular hexagons with a common long diagonal and their planes perpendicular. Now if we take A, B in the same hexagon, then we can find C, D in the same hexagon. If we take A in one and B in the other, then we may take C at the opposite end of a long diagonal from A, and D at the opposite end of a long diagonal from B. 

Problem A3

a and b are real numbers for which the equation x⁴ + ax³ + bx² + ax + 1 = 0 has at least one real solution. Find the least possible value of a² + b².

Solution

Put y = x + 1/x and the equation becomes y² + ay + b - 2 = 0, which has solutions y = -a/2 ±√(a² + 8 - 2b)/2. We require |y| ≥ 2 for the original equation to have a real root and hence we need |a| + √(a² + 8 - 4b) ≥ 4. Squaring gives 2|a| - b ≥ 2. Hence a² + b² ≥ a² + (2 - 2|a|)² = 5a² - 8|a| + 4 = 5(|a| - 4/5)² + 4/5. So the least possible value of a² + b² is 4/5, achieved when a = 4/5, b = -2/5. In this case, the original equation is x⁴ + 4/5 x³ - 2/5 x² + 4/5 x + 1 = (x + 1)²(x² - 6/5 x + 1). 

Problem B1

A soldier needs to sweep a region with the shape of an equilateral triangle for mines. The detector has an effective radius equal to half the altitude of the triangle. He starts at a vertex of the triangle. What path should he follow in order to travel the least distance and still sweep the whole region?

Solution

In particular he must sweep the other two vertices. Let us take the triangle to be ABC, with side 1 and assume the soldier starts at A. So the path must intersect the circles radius √3/4 centered on the other two vertices. Let us look for the shortest path of this type. Suppose it intersects the circle center B at X and the circle center C at Y, and goes first to X and then to Y. Clearly the path from A to X must be a straight line and the path from X to Y must be a straight line. Moreover the shortest path from X to the circle center C follows the line XC and has length AX + XC - √3/4. So we are looking for the point X which minimises AX + XC.

Consider the point P where the altitude intersects the circle. By the usual reflection argument the distance AP + PC is shorter than the distance AP' + P'C for any other point P' on the line perpendicular to the altitude through P. Moreover for any point X on the circle, take AX to cut the line at P'. Then AX + XC > AP' + P'C > AP + PC.

It remains to check that the three circles center A, X, Y cover the triangle. In fact the circle center X covers the whole triangle except for a small portion near A and a small portion near C, which are covered by the triangles center A and Y. 

Problem B2

G is a set of non-constant functions f. Each f is defined on the real line and has the form f(x) = ax + b for some real a, b. If f and g are in G, then so is fg, where fg is defined by fg(x) = f(g(x)). If f is in G, then so is the inverse f^-1. If f(x) = ax + b, then f^-1(x) = x/a - b/a. Every f in G has a fixed point (in other words we can find x_f such that f(x_f) = x_f. Prove that all the functions in G have a common fixed point.

Solution

f(x) = ax + b has fixed point b/(1-a). If a = 1, then b must be 0, and any point is a fixed point. So suppose f(x) = ax + b and g(x) = ax + b' are in G. Then h the inverse of f is given by h(x) = x/a - b/a, and hg(x) = x + b'/a - b/a. This is in G, so we must have b' = b.

Suppose f(x) = ax + b, and g(x) = cx + d are in G. Then fg(x) = acx + (ad + b), and gf(x) = acx + (bc + d). We must have ad + b = bc + d and hence b/(1-a) = c/(1-d), in other words f and g have the same fixed point. 

Problem B3

a₁, a₂, ... , a_n are positive reals, and q satisfies 0 < q < 1. Find b₁, b₂, ... , b_n such that:

(a)  a_i < b_i for i = 1, 2, ... , n,

(b)  q < b_i+1/b_i < 1/q for i = 1, 2, ... , n-1,

(c)  b₁ + b₂ + ... + b_n < (a₁ + a₂ + ... + a_n)(1 + q)/(1 - q).

Solution

We notice that the constraints are linear, in the sense that if b_i is a solution for a_i, q, and b_i' is a solution for a_i', q, then for any k, k' > 0 a solution for ka_i + k'a_i', q is kb_i + k'b_i'. Also a "near" solution for a_h = 1, other a_i = 0 is b₁ = q^h-1, b₂ = q^h-2, ... , b_h-1 = q, b_h = 1, b_h+1 = q, ... , b_n = q^n-h. "Near" because the inequalities in (a) and (b) are not strict.

However, we might reasonably hope that the inequalities would become strict in the linear combination, and indeed that is true. Define b_r = q^r-1a₁ + q^r-2a₂ + ... + qa_r-1 + a_r + qa_r+1 + ... + q^n-ra_n. Then we may easily verify that (a) - (c) hold.

Solutions are also available in:   Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.