13th International Mathematical Olympiad 1971 Problems & Solutions

A1.  Let E_n = (a₁ - a₂)(a₁ - a₃) ... (a₁ - a_n) + (a₂ - a₁)(a₂ - a₃) ... (a₂ - a_n) + ... + (a_n - a₁)(a_n - a₂) ... (a_n - a_n-1). Let S_n be the proposition that E_n ≥ 0 for all real a_i. Prove that S_n is true for n = 3 and 5, but for no other n > 2.

A2.  Let P₁ be a convex polyhedron with vertices A₁, A₂, ... , A₉. Let P_i be the polyhedron obtained from P₁ by a translation that moves A₁ to A_i. Prove that at least two of the polyhedra P₁, P₂, ... , P₉ have an interior point in common.

A3.  Prove that we can find an infinite set of positive integers of the form 2ⁿ - 3 (where n is a positive integer) every pair of which are relatively prime.

B1.  All faces of the tetrahedron ABCD are acute-angled. Take a point X in the interior of the segment AB, and similarly Y in BC, Z in CD and T in AD. (a)  If angle DAB + angle BCD ≠ angle CDA + angle ABC, then prove that none of the closed paths XYZTX has minimal length;

(b)  If angle DAB + angle BCD =angle CDA + angle ABC, then there are infinitely many shortest paths XYZTX, each with length 2 AC sin k, where 2k = angle BAC + angle CAD + angle DAB.

B2.  Prove that for every positive integer m we can find a finite set S of points in the plane, such that given any point A of S, there are exactly m points in S at unit distance from A.

B3.  Let A = (a_ij), where i, j = 1, 2, ... , n, be a square matrix with all a_ij non-negative integers. For each i, j such that a_ij = 0, the sum of the elements in the ith row and the jth column is at least n. Prove that the sum of all the elements in the matrix is at least n²/2. 

Solutions

Problem A1

Let E_n = (a₁ - a₂)(a₁ - a₃) ... (a₁ - a_n) + (a₂ - a₁)(a₂ - a₃) ... (a₂ - a_n) + ... + (a_n - a₁)(a_n - a₂) ... (a_n - a_n-1). Let S_n be the proposition that E_n ≥ 0 for all real a_i.

Prove that S_n is true for n = 3 and 5, but for no other n > 2.

 

Solution

Take a₁ < 0, and the remaining a_i = 0. Then E_n = a₁^n-1 < 0 for n even, so the proposition is false for even n.

Suppose n ≥ 7 and odd. Take any c > a > b, and let a₁ = a, a₂ = a₃ = a₄= b, and a₅ = a₆ = ... = a_n = c. Then E_n = (a - b)³(a - c)^n-4 < 0. So the proposition is false for odd n ≥ 7.

Assume a₁ ≥ a₂ ≥ a₃. Then in E₃ the sum of the first two terms is non-negative, because (a₁ - a₃) ≥ (a₂ - a₃). The last term is also non-negative. Hence E₃ ≥ 0, and the proposition is true for n = 3.

It remains to prove S₅. Suppose a₁ ≥ a₂ ≥ a₃ ≥ a₄ ≥ a₅. Then the sum of the first two terms in E₅ is (a₁ - a₂){(a₁ - a₃)(a₁ - a₄)(a₁ - a₅) - (a₂ - a₃)(a₂ - a₄)(a₂ - a₅)} ≥ 0. The third term is non-negative (the first two factors are non-positive and the last two non-negative). The sum of the last two terms is: (a₄ - a₅){(a₁ - a₅)(a₂ - a₅)(a₃ - a₅) - (a₁ - a₄)(a₂ - a₄)(a₃ - a₄)} ≥ 0. Hence E₅ ≥ 0. 

Problem A2

Let P₁ be a convex polyhedron with vertices A₁, A₂, ... , A₉. Let P_i be the polyhedron obtained from P₁ by a translation that moves A₁ to A_i. Prove that at least two of the polyhedra P₁, P₂, ... , P₉ have an interior point in common.

 

Solution

The result is false for 8 vertices - for example, the cube. We get 8 cubes, with only faces in common, forming a cube 8 times as large.

This suggests a trick. Each P_i is contained in D, the polyhedron formed from P₁ by doubling the scale. Take A₁ as the origin and take the vertex B_i to have twice the coordinates of A_i. Given a point X inside P₁, the midpoint of P_iX must lie in P₁ by convexity. Hence the point with doubled coordinates, which is obtained by adding the coordinates of A_i to the coordinates of X, lies in D. In other words every point of P_i lies in D. But the volume of D is 8 times the volume of P₁, which is less than the sum of the volumes of P₁, ... , P₉. 

Problem A3

Prove that we can find an infinite set of positive integers of the form 2ⁿ - 3 (where n is a positive integer) every pair of which are relatively prime.

 

Solution

We show how to enlarge a set of r such integers to a set of r+1. So suppose 2^n₁ - 3, ... , 2^n_r - 3 are all relatively prime. The idea is to find 2ⁿ - 1 divisible by m = (2^n₁ - 3) ... (2^n_r - 3), because then 2ⁿ - 3 must be relatively prime to all of the factors of m. At least two of 2⁰, 2¹, ... , 2^m must be congruent mod m. So suppose m₁ > m₂ and 2^m₁ = 2^m₂ (mod m), then we must have 2^{m₁ - m₂} - 1 = 0 (mod m), since m is odd. So we may take n_r+1 to be m₁ - m₂. 

Problem B1

All faces of the tetrahedron ABCD are acute-angled. Take a point X in the interior of the segment AB, and similarly Y in BC, Z in CD and T in AD.

(a)  If ∠DAB + ∠BCD ≠ ∠CDA + ∠ABC, then prove that none of the closed paths XYZTX has minimal length;

(b)  If ∠DAB + ∠BCD = ∠CDA + ∠ABC, then there are infinitely many shortest paths XYZTX, each with length 2 AC sin k, where 2k = ∠BAC + ∠CAD + ∠DAB.

 

Solution

The key is to pretend the tetrahedron is made of cardboard, cut it along three edges and unfold it. Suppose we do this to get the hexagon CAC'BDB'. Now the path is a line joining Y on B'C to Y' on the opposite side BC' of the hexagon. Clearly this line must be straight for a minimal path. If B'C and BC' are parallel, then we can take Y anywhere on the side and the minimal path length is the expression given.

But if they are not parallel, then the minimal path will come from an extreme position. Suppose CC' < BB'. If the interior angle CAC' is less than 180^o, then the minimal path is obtained by taking Y at C. But this does not meet the requirement that Y be an interior point of the edge, so there is no minimal path in the permitted set. If the interior angle CAC' is greater than 180, then the minimal path is obtained by taking X and T at A. Again this is not permitted.

The problem therefore reduces to finding the condition for B'C and BC' to be parallel. This is evidently angles BCD + DCA + CAD + BAD + BAC + ACB = 360^o. But DCA + CAD = 180^o - ADC, and BAC + ACB = 180^o - ABC, so we obtain the condition given. 

Problem B2

Prove that for every positive integer m we can find a finite set S of points in the plane, such that given any point A of S, there are exactly m points in S at unit distance from A.

 

Solution

Take a₁, a₂, ... , a_m to be points a distance 1/2 from the origin O. Form the set of 2^m points ±a₁ ±a₂ ± ... ±a_m. Given such a point, it is at unit distance from the m points with just one coefficient different. So we are home, provided that we can choose the a_i to avoid any other pairs of points being at unit distance, and to avoid any degeneracy (where some of the 2^m points coincide).

The distance between two points in the set is |c₁a₁ + c₂a₂ + ... + c_ma_m|, where c_i = 0, 2 or -2. So let us choose the a_i inductively. Suppose we have already chosen up to m. The constraints on a_m+1 are that we do not have |c₁a₁ + c₂a₂ + ... + c_ma_m + 2a_m+1| equal to 0 or 1 for any c_i = 0, 2 or -2, apart from the trivial cases of all c_i = 0. Each | | = 0 rules out a single point and each | | = 1 rules out a circle which intersects the circle radius 1/2 about the origin at 2 points and hence rules out two points. So the effect of the constraints is to rule out a finite number of points, whereas we have uncountably many to choose from. 

Problem B3

Let A = (a_ij), where i, j = 1, 2, ... , n, be a square matrix with all a_ij non-negative integers. For each i, j such that a_ij = 0, the sum of the elements in the ith row and the jth column is at least n. Prove that the sum of all the elements in the matrix is at least n²/2.

 

Solution

Let x be the smallest row or column sum. If x >= n/2, then we are done, so assume x < n/2. Suppose it is a row. (If not, interchange rows and columns.) The number of non-zero elements in the row, y, must also satisfy y < n/2, since each non-zero element is at least 1. Now move across this row summing the columns. The y columns with a non-zero element have sum at least x (by the definition of x). The n - y columns with a zero have sum at least n - x. Hence the total sum is at least xy + (n - x)(n - y) = n²/2 + (n - 2x)(n - 2y)/2 > n²/2.

The result is evidently best possible, because we can fill the matrix alternately with zeros and ones (so that a_ij = 1 if i and j are both odd or both even, 0 otherwise). For n even, every row and column has n/2 1s, so the condition is certainly satisfied and the total sum is n²/2. For n odd, odd numbered rows have (n+1)/2 1s and even numbered one less. But the only zeros are in positions which have either the row or the column odd-numbered, so the sum in such cases is n as required. The total sum is n²/2 + 1/2. Alternatively, for n even, we could place n/2 down the main diagonal.