18th International Mathematical Olympiad 1976 Problems & Solutions

A1.  A plane convex quadrilateral has area 32, and the sum of two opposite sides and a diagonal is 16. Determine all possible lengths for the other diagonal.

A2.  Let P₁(x) = x² - 2, and P_i+1 = P₁(P_i(x)) for i = 1, 2, 3, ... . Show that the roots of P_n(x) = x are real and distinct for all n.

A3.  A rectangular box can be completely filled with unit cubes. If one places as many cubes as possible, each with volume 2, in the box, with their edges parallel to the edges of the box, one can fill exactly 40% of the box. Determine the possible dimensions of the box.

B1.  Determine the largest number which is the product of positive integers with sum 1976.

B2.  n is a positive integer and m = 2n. a_ij = 0, 1 or -1 for 1 ≤ i ≤ n, 1 ≤ j ≤ m. The m unknowns x₁, x₂, ... , x_m satisfy the n equations:       a_i1x₁ + a_i2x₂ + ... + a_imx_m = 0,

for i = 1, 2, ... , n. Prove that the system has a solution in integers of absolute value at most m, not all zero.

B3.  The sequence u₀, u₁, u₂, ... is defined by: u₀= 2, u₁ = 5/2, u_n+1 = u_n(u_n-1² - 2) - u₁ for n = 1, 2, ... . Prove that [u_n] = 2^{(2n - (-1)n)/3}, where [x] denotes the greatest integer less than or equal to x. 

Solutions

Problem A1

A plane convex quadrilateral has area 32, and the sum of two opposite sides and a diagonal is 16. Determine all possible lengths for the other diagonal.

 

Solution

At first sight, the length of the other diagonal appears unlikely to be significantly constrained. However, a little experimentation shows that it is hard to get such a low value as 16. This suggests that 16 may be the smallest possible value.

If the diagonal which is part of the 16 has length x, then the area is the sum of the areas of two triangles base x, which is xy/2, where y is the sum of the altitudes of the two triangles. y must be at most (16 - x), with equality only if the two triangles are right-angled. But x(16 - x)/2 = (64 - (x - 8)²)/2 ≤ 32 with equality only iff x = 8. Thus the only way we can achieve the values given is with one diagonal length 8 and two sides perpendicular to this diagonal with lengths totalling 8. But in this case the other diagonal has length 8√2. 

Problem A2

Let P₁(x) = x² - 2, and P_i+1 = P₁(P_i(x)) for i = 1, 2, 3, ... . Show that the roots of P_n(x) = x are real and distinct for all n.

 

Solution

We show that the graph of P_n can be divided into 2ⁿ lines each joining the top and bottom edges of the square side 4 centered on the origin (vertices (2,2), (-2,2), (-2,-2), (-2,2) ). We are then home because the upward sloping diagonal of the square, which represents the graph of y = x, must cut each of these lines and hence give 2ⁿ distinct real roots of P_n(x) = x in the range [-2,2]. But P_n is a polynomial of degree 2ⁿ, so it has exactly 2ⁿ roots. Hence all its roots are real and distinct.

We prove the result about the graph by induction. It is true for n = 1: the first line is the graph from x = -2 to 0, and the second line is the graph from 0 to 2. So suppose it is true for n. Then P₁ turns each of the 2ⁿ lines for P_n into two lines for P_n+1, so the result is true for n+1.

Alternative solution from Arthur Engel, Problem-Solving Strategies, Springer 1998 [Problem books in mathematics series], ISBN 0387982191. A rather good training book.

Put x = 2 cos t (so we are restricting attention to -2 ≤ x ≤ 2). Then we find P_n(x) = 2 cos 2ⁿt, so the equation P_n(x) = x becomes cos 2ⁿt = cos t. By inspection, has the 2ⁿ solutions t = 2kπ/(2ⁿ - 1) and t = 2kπ/(2ⁿ + 1), giving 2ⁿ distinct solutions in x.  

Problem A3

A rectangular box can be completely filled with unit cubes. If one places as many cubes as possible, each with volume 2, in the box, with their edges parallel to the edges of the box, one can fill exactly 40% of the box. Determine the possible dimensions of the box.

 

Solution

Answer: 2 x 3 x 5 or 2 x 5 x 6.

This is somewhat messy. The basic idea is that the sides cannot be too long, because then the ratio becomes too big. Let k denote the (real) cube root of 2. Given any integer n, let n' denote the least integer such that n'k <= n. Let the sides of the box be a ≤ b ≤ c. So we require 5a'b'c' = abc (*).

It is useful to derive n' for small n: 1' = 0, 2' = 1, 3' = 2, 4' = 3, 5' = 3, 6' = 4, 7' = 5, 8' = 6, 9' = 7, 10' = 7.

Clearly n'k ≥ n-2. But 6³ > 0.4 8³, and hence (n'k)³ ≥ (n - 2)³ > 0.4 n³ for all n ≥ 8. We can check directly that (n'k)³ > 0.4 n³ for n = 3, 4, 5, 6, 7. So we must have a = 2 (we cannot have a = 1, because 1' = 0).

From (*) we require b or c to be divisible by 5. Suppose we take it to be 5. Then since 5' = 3, the third side n must satisfy: n' = 2/3 n. We can easily check that 2k/3 < 6/7 and hence (2/3 nk + 1 ) < n for n ≥ 7, so n' > 2/3 n for n ≥ 7. This just leaves the values n = 3 and n = 6 to check (since n' = 2/3 n is integral so n must be a multiple of 3). Referring to the values above, both these work. So this gives us two possible boxes: 2 x 3 x 5 and 2 x 5 x 6.

The only remaining possibility is that the multiple of 5 is at least 10. But then it is easy to check that if it is m then m'/m ≥ 7/10. It follows from (*) that the third side r must satisfy r'/r <= 4/7. But using the limit above and referring to the small values above, this implies that r must be 2. So a = b = 2. But now c must satisfy c' = 4/5 c. However, that is impossible because 4/5 k > 1. 

Problem B1

Determine the largest number which is the product of positive integers with sum 1976.

 

Solution

Answer: 2·3⁶⁵⁸.

There cannot be any integers larger than 4 in the maximal product, because for n > 4, we can replace n by 3 and n - 3 to get a larger product. There cannot be any 1s, because there must be an integer r > 1 (otherwise the product would be 1) and r + 1 > 1.r. We can also replace any 4s by two 2s leaving the product unchanged. Finally, there cannot be more than two 2s, because we can replace three 2s by two 3s to get a larger product. Thus the product must consist of 3s, and either zero, one or two 2s. The number of 2s is determined by the remainder on dividing the number 1976 by 3.

1976 = 3·658 + 2, so there must be just one 2, giving the product 2·3⁶⁵⁸.  

Problem B2

n is a positive integer and m = 2n. a_ij = 0, 1 or -1 for 1 ≤ i ≤ n, 1 ≤ j ≤ m. The m unknowns x₁, x₂, ... , x_m satisfy the n equations:

      a_i1x₁ + a_i2x₂ + ... + a_imx_m = 0,

for i = 1, 2, ... , n. Prove that the system has a solution in integers of absolute value at most m, not all zero.

 

Solution

We use a counting argument. If the modulus of each x_i is at most n, then each of the linear combinations has a value between -2n² and 2n², so there are at most (4n² + 1) possible values for each linear combination and at most (2n² + 1)ⁿ possible sets of values. But there are 2n+1 values for each x_i with modulus at most n, and hence (2n+1)²ⁿ = (4n²+4n+1)ⁿ sets of values. So two distinct sets must give the same set of values for the linear combinations. But now if these sets are x_i and x_i', then the values x_i-x_i' give zero for each linear combination, and have modulus at most 2n. Moreover they are not all zero, since the two sets of values were distinct. 

Problem B3

The sequence u₀, u₁, u₂, ... is defined by: u₀= 2, u₁ = 5/2, u_n+1 = u_n(u_n-1² - 2) - u₁ for n = 1, 2, ... . Prove that [u_n] = 2^{(2n - (-1)n)/3}, where [x] denotes the greatest integer less than or equal to x.

 

Solution

Experience with recurrence relations suggests that the solution is probably the value given for [u_n] plus its inverse. It is straightforward to verify this guess by induction.

Squaring u_n-1 gives the sum of positive power of 2, its inverse and 2. So u_n-1 - 2 = the sum of a positive power of 2 and its inverse. Multiplying this by u_n gives a positive power of 2 + its inverse + 2 + 1/2, and we can check that the power of 2 is correct for u_n+1. 

 

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.