6th International Mathematical Olympiad 1964 Problems & Solutions

A1. (a)  Find all natural numbers n for which 7 divides 2ⁿ - 1.

(b)  Prove that there is no natural number n for which 7 divides 2ⁿ + 1.

A2.  Suppose that a, b, c are the sides of a triangle. Prove that:     a²(b + c - a) + b²(c + a - b) + c²(a + b - c) ≤ 3abc.

A3.  Triangle ABC has sides a, b, c. Tangents to the inscribed circle are constructed parallel to the sides. Each tangent forms a triangle with the other two sides of the triangle and a circle is inscribed in each of these three triangles. Find the total area of all four inscribed circles.

B1.  Each pair from 17 people exchange letters on one of three topics. Prove that there are at least 3 people who write to each other on the same topic. [In other words, if we color the edges of the complete graph K₁₇ with three colors, then we can find a triangle all the same color.]

B2.  5 points in a plane are situated so that no two of the lines joining a pair of points are coincident, parallel or perpendicular. Through each point lines are drawn perpendicular to each of the lines through two of the other 4 points. Determine the maximum number of intersections these perpendiculars can have.

B3.  ABCD is a tetrahedron and D₀ is the centroid of ABC. Lines parallel to DD₀ are drawn through A, B and C and meet the planes BCD, CAD and ABD in A₀, B₀, and C₀ respectively. Prove that the volume of ABCD is one-third of the volume of A₀B₀C₀D₀. Is the result true if D₀ is an arbitrary point inside ABC? 

Solutions

Problem A1

(a)  Find all natural numbers n for which 7 divides 2ⁿ - 1.
(b)  Prove that there is no natural number n for which 7 divides 2ⁿ + 1.

Solution

2³ = 1 (mod 7). Hence 2^3m = 1 (mod 7), 2^3m+1 = 2 (mod 7), and 2^3m+2 = 4 (mod 7). Hence we never have 7 dividing 2ⁿ + 1, and 7 divides 2ⁿ - 1 iff 3 divides n. 

Problem A2

Suppose that a, b, c are the sides of a triangle. Prove that:

    a²(b + c - a) + b²(c + a - b) + c²(a + b - c) ≤ 3abc.

Solution

The condition that a, b, c be the sides of a triangle, together with the appearance of quantities like a + b - c is misleading. The inequality holds for any a , b, c ≥ 0.

At most one of (b+c-a), (c+a-b), (a+b-c) can be negative. If one of them is negative, then certainly:

        abc ≥ (b + c - a)(c + a - b)(a + b - c) (*)

since the lhs is non-negative and the rhs is non-positive.

(*) is also true if none of them is negative. For then the arithmetic/geometric mean on b + c - a, c + a - b gives:
        c² ≥ (b + c - a)(c + a - b).

Similarly for a² and b². Multiplying and taking the square root gives (*). Multiplying out easily gives the required result. 

Problem A3

Triangle ABC has sides a, b, c. Tangents to the inscribed circle are constructed parallel to the sides. Each tangent forms a triangle with the other two sides of the triangle and a circle is inscribed in each of these three triangles. Find the total area of all four inscribed circles.

Solution

This is easy once you realize that the answer is not nice and the derivation a slog. Use r = 2·area/perimeter and Heron's formula: area k is given by 16k² = (a + b + c)(b + c - a)(c + a - b)(a + b - c).

The small triangles at the vertices are similar to the main triangle and smaller by a factor (h - 2r)/h, where h is the relevant altitude. For the triangle opposite side a: (h - 2r)/h = 1 - 2(2k/p)/(2k/a) = 1 - 2a/p = (b + c - a)/(a + b + c).

Hence the total area is ((a + b + c)² + (b + c - a)² + (c + a - b)² + (a + b - c)²)/(a + b + c)² pi r² =

(a² + b² + c²).pi.(b + c - a)(c + a - b)(a + b - c)/(a + b + c)³.

Problem B1

Each pair from 17 people exchange letters on one of three topics. Prove that there are at least 3 people who write to each other on the same topic. [In other words, if we color the edges of the complete graph K₁₇ with three colors, then we can find a triangle all the same color.]

Solution

Take any person. He writes to 16 people, so he must write to at least 6 people on the same topic. If any of the 6 write to each other on that topic, then we have a group of three writing to each other on the same topic. So assume they all write to each other on the other two topics. Take any of them, B. He must write to at least 3 of the other 5 on the same topic. If two of these write to each other on this topic, then they form a group of three with B. Otherwise, they must all write to each other on the third topic and so from a group of three. 

Problem B2

5 points in a plane are situated so that no two of the lines joining a pair of points are coincident, parallel or perpendicular. Through each point lines are drawn perpendicular to each of the lines through two of the other 4 points. Determine the maximum number of intersections these perpendiculars can have.

Solution

It is not hard to see that the required number is at most 315. But it is not at all obvious how you prove it actually is 315, short of calculating the 315 points intersection for a specific example.

Call the points A, B, C, D, E. Given one of the points, the other 4 points determine 6 lines, so there are 6 perpendiculars through the given point and hence 30 perpendiculars in all. These determine at most 30.29/2 = 435 points of intersection. But some of these necessarily coincide. There are three groups of coincidences. The first is that the 6 perpendiculars through A meet in one point (namely A), not the expected 15. So we lose 5.14 = 70 points. Second, the lines through C, D and E perpendicular to AB are all parallel, and do not give the expected 3 points of intersection, so we lose another 10.3 = 30 points. Third, the line through A perpendicular to BC is an altitude of the triangle ABC, as are the lines through B perpendicular to AC, and the through C perpendicular to AB. So we only get one point of intersection instead of three, thus losing another 10.2 = 20 points. These coincidences are clearly all distinct (the categories do not overlap), so they bring us down to a maximum of 435 - 120 =315.

There is no obvious reason why there should be any further coincidences. But that is not quite the same as proving that there are no more. Indeed, for particular positions of the points A, B, C, D, E we can certainly arrange for additional coincidences (the constraints given in the problem are not sufficient to prevent additional coincidences). So we have to prove that it is possible to arrange the points so that there are no additional coincidences. I cannot see how to do this, short of exhibiting a particular set of points, which would be extremely tiresome. Apparently the contestants were instructed verbally that they did not have to do it. 

Problem B3

ABCD is a tetrahedron and D₀ is the centroid of ABC. Lines parallel to DD₀ are drawn through A, B and C and meet the planes BCD, CAD and ABD in A₀, B₀, and C₀ respectively. Prove that the volume of ABCD is one-third of the volume of A₀B₀C₀D₀. Is the result true if D₀ is an arbitrary point inside ABC?

Solution

Yes, indeed it is true for an arbitrary point in the plane of ABC not on any of the lines AB, BC, CA

Take D as the origin. Let A, B, C be the points a, b, c respectively. Then D₀ is pa + qb + rc with p + q + r = 1 and p, q, r > 0. So a point on the line parallel to DD₀ through A is a + s(pa + qb + rc. It is also in the plane DBC if s = -1/p, so A₀ is the point - q/p b - r/p c. Similarly, B₀ is - p/q a - r/q c, and C₀ is - p/r a - q/r b.

The volume of ABCD is 1/6 |a x b.c| and the volume of A₀B₀C₀D₀ is 1/6 |(pa + (q + q/p)b + (r + r/p)c) x ((p + p/q)a + qb + (r + r/q)c).((p + p/r)a + (q + q/r)b + rc)|

Thus vol A₀B₀C₀D₀/vol ABCD = abs value of the determinant:

| p        q + q/p  r + r/p |

| p + p/q  q        r + r/q |

| p + p/r  q + q/r  r       |

which is easily found to be 2 + p + q + r = 3.

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.