14th International Mathematical Olympiad 1972 Problems & Solutions

A1.  Given any set of ten distinct numbers in the range 10, 11, ... , 99, prove that we can always find two disjoint subsets with the same sum.

A2.  Given n > 4, prove that every cyclic quadrilateral can be dissected into n cyclic quadrilaterals.

A3.  Prove that (2m)!(2n)! is a multiple of m!n!(m+n)! for any non-negative integers m and n.

B1.  Find all positive real solutions to:         (x₁² - x₃x₅)(x₂² - x₃x₅) ≤ 0

        (x₂² - x₄x₁)(x₃² - x₄x₁) ≤ 0

        (x₃² - x₅x₂)(x₄² - x₅x₂) ≤ 0

        (x₄² - x₁x₃)(x₅² - x₁x₃) ≤ 0

        (x₅² - x₂x₄)(x₁² - x₂x₄) ≤ 0

B2.  f and g are real-valued functions defined on the real line. For all x and y, f(x + y) + f(x - y) = 2f(x)g(y). f is not identically zero and |f(x)| ≤ 1 for all x. Prove that |g(x)| ≤ 1 for all x.

B3.  Given four distinct parallel planes, prove that there exists a regular tetrahedron with a vertex on each plane. 

Solutions

Problem A1

Given any set of ten distinct numbers in the range 10, 11, ... , 99, prove that we can always find two disjoint subsets with the same sum.

 

Solution

The number of non-empty subsets is 2¹⁰ - 1 = 1023. The sum of each subset is at most 90 + ... + 99 = 945, so there must be two distinct subsets A and B with the same sum. A \ B and B \ A are disjoint subsets, also with the same sum. 

Problem A2

Given n > 4, prove that every cyclic quadrilateral can be dissected into n cyclic quadrilaterals.

 

Solution

A little tinkering soon shows that it is easy to divide a cyclic quadrilateral ABCD into 4 cyclic quadrilaterals. Take a point P inside the quadrilateral and take an arbitrary line PK joining it to AB. Now take L on BC so that ∠KPL = 180^o - ∠B (thus ensuring that KPLB is cyclic), then M on CD so that ∠LPM = 180^o - ∠C, then N on AD so that ∠MPN = 180^o - ∠D. Then ∠NPK = 180^o - ∠A. We may need to impose some restrictions on P and K to ensure that we can obtain the necessary angles. It is not clear, however, what to do next.

The trick is to notice that the problem is easy if two sides are parallel. For then we may take arbitrarily many lines parallel to the parallel sides and divide the original quadrilateral into any number of parts.

So we need to arrange our choice of P and K so that one of the new quadrilaterals has parallel sides. But that is easy, since K is arbitrary. So take PK parallel to AD, then we must also have PL parallel to CD.

It remains to consider how we ensure that the points lie on the correct sides. Consider first K and L. K cannot lie on AD since PK is parallel to AD, and we can avoid it lying on BC by taking P sufficiently close to D. Similarly, taking P sufficiently close to D ensures that L lies on BC. Now suppose that M and N are both on AD. Then if we keep K fixed and move P closer to CD, N will move on to CD, leaving M on AD. 

Problem A3

Prove that (2m)!(2n)! is a multiple of m!n!(m+n)! for any non-negative integers m and n.

 

Solution

The trick is to find a recurrence relation for f(m,n) = (2m)!(2n)!/(m!n!(m+n)!). In fact, f(m,n) = 4 f(m,n-1) - f(m+1,n-1), which is sufficient to generate all the f(m,n), given that f(m,0) = (2m)!/(m!m!), which we know to be integeral. 

Problem B1

Find all positive real solutions to:

        (x₁² - x₃x₅)(x₂² - x₃x₅) ≤ 0
        (x₂² - x₄x₁)(x₃² - x₄x₁) ≤ 0
        (x₃² - x₅x₂)(x₄² - x₅x₂) ≤ 0
        (x₄² - x₁x₃)(x₅² - x₁x₃) ≤ 0
        (x₅² - x₂x₄)(x₁² - x₂x₄) ≤ 0

 

Solution

Answer: x₁ = x₂ = x₃ = x₄ = x₅.

The difficulty with this problem is that it has more information than we need. There is a neat solution in Greitzer which shows that all we need is the sum of the 5 inequalities, because one can rewrite that as (x₁x₂ - x₁x₄)² + (x₂x₃ - x₂x₅)² + ... + (x₅x₁ - x₅x₃)² + (x₁x₃ - x₁x₅)² + ... + (x₅x₂ - x₅x₄)² ≤ 0. The difficulty is how one ever dreams up such an idea!

The more plodding solution is to break the symmetry by taking x₁ as the largest. If the second largest is x₂, then the first inequality tells us that x₁² or x₂² = x₃x₅. But if x₃ and x₅ are unequal, then the larger would exceed x₁ or x₂. Contradiction. Hence x₃ = x₅ and also equals x₂ or x₁. If they equal x₁, then they would also equal x₂ (by definition of x₂), so in any case they must equal x₂. Now the second inequality gives x₂ = x₁x₄. So either all the numbers are equal, or x₁ > x₂ = x₃ = x₅ > x₄. But in the second case the last inequality is violated. So the only solution is all numbers equal.

If the second largest is x₅, then we can use the last inequality to deduce that x₂ = x₄ = x₅ and proceed as before.

If the second largest is x₃, then the fourth inequality gives that x₁ = x₃ = x₅ or x₁ = x₃ = x₄. In the first case, x₅ is the second largest and we are home already. In the second case, the third inequality gives x₃² = x₂x₅ and hence x₃ = x₂ = x₅ (or one of x₂, x₅ would be larger than the second largest). So x₅ is the second largest and we are home.

Finally, if the second largest is x₄, then the second inequality gives x₁ = x₂ = x₄ or x₁ = x₃ = x₄. Either way, we have a case already covered and so the numbers are all equal. 

Problem B2

f and g are real-valued functions defined on the real line. For all x and y, f(x + y) + f(x - y) = 2f(x)g(y). f is not identically zero and |f(x)| ≤ 1 for all x. Prove that |g(x)| ≤ 1 for all x.

 

Solution

Let k be the least upper bound for |f(x)|. Suppose |g(y)| > 1. Take any x with |f(x)| > 0, then 2k ≥ |f(x+y)| + |f(x-y)| ≥ |f(x+y) + f(x-y)| = 2|g(y)||f(x)|, so |f(x)| < k/|g(y)|. In other words, k/|g(y)| is an upper bound for |f(x)| which is less than k. Contradiction. 

Problem B3

Given four distinct parallel planes, prove that there exists a regular tetrahedron with a vertex on each plane.

 

Solution

Intuitively, we can place A and B on the two outer planes with AB perpendicular to the planes. Then tilt AB in one direction until we bring C onto one of the middle planes (keeping A and B on the outer planes), then tilt AB the other way (keeping A, B, C on their respective planes) until D gets onto the last plane.

Take A as the origin. Let the vectors AB, AC, AD be b, c, d. Take p as one of the outer planes. Let the distances to the other planes be e, f, g. Now we find a vector n satisfying: n.b = e, n.c = f, n.d = g. This is a system of three equations in three unknowns with non-zero determinant (because b.c x d is non-zero), so it has a solution n. Scale the tetrahedron by |n|, orient p perpendicular to n/|n|, then B, C, D will be on the other planes as required. 

 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.