33rd International Mathematical Olympiad 1992 Problems & Solutions

A1.  Find all integers a, b, c satisfying 1 < a < b < c such that (a - 1)(b -1)(c - 1) is a divisor of abc - 1.

A2.  Find all functions f defined on the set of all real numbers with real values, such that f(x² + f(y)) = y + f(x)² for all x, y.

A3.  Consider 9 points in space, no 4 coplanar. Each pair of points is joined by a line segment which is colored either blue or red or left uncolored. Find the smallest value of n such that whenever exactly n edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

B1.  L is a tangent to the circle C and M is a point on L. Find the locus of all points P such that there exist points Q and R on L equidistant from M with C the incircle of the triangle PQR.

B2.  Let S be a finite set of points in three-dimensional space. Let S_x, S_y, S_z be the sets consisting of the orthogonal projections of the points of S onto the yz-plane, zx-plane, xy-plane respectively. Prove that:       |S|² ≤ |S_x| |S_y| |S_z|, where |A| denotes the number of points in the set A.

[The orthogonal projection of a point onto a plane is the foot of the perpendicular from the point to the plane.]

B3.  For each positive integer n, S(n) is defined as the greatest integer such that for every positive integer k ≤ S(n), n² can be written as the sum of k positive squares. (a)  Prove that S(n) ≤ n² - 14 for each n ≥ 4.

(b)  Find an integer n such that S(n) = n² - 14.

(c)  Prove that there are infinitely many integers n such that S(n) = n² - 14. 

Solutions

Problem A1

Find all integers a, b, c satisfying 1 < a < b < c such that (a - 1)(b -1)(c - 1) is a divisor of abc - 1.

 

Solution

Answer: a = 2, b = 4, c = 8; or a = 3, b = 5, c = 15.

Let k = 2^1/3. If a ≥ 5, then k(a - 1) > a. [Check: (k(a - 1)³ - a³ = a³ - 6a² + 6a - 2. For a ≥ 6, a³ ≥ 6a² and 6a > 2, so we only need to check a = 5: 125 - 150 + 30 - 2 = 3.] We know that c > b > a, so if a ≥ 5, then 2(a - 1)(b - 1)(c - 1) > abc > abc - 1. So we must have a = 2, 3 or 4.

Suppose abc - 1 = n(a - 1)(b - 1)(c - 1). We consider separately the cases n = 1, n = 2 and n ≥ 3. If n = 1, then a + b + c = ab + bc + ca. But that is impossible, because a, b, c are all greater than 1 and so a < ab, b < bc and c < ca.

Suppose n = 2. Then abc - 1 is even, so all a, b, c are odd. In particular, a = 3. So we have 4(b - 1)(c - 1) = 3bc - 1, and hence bc + 5 = 4b + 4c. If b >= 9, then bc >= 9c > 4c + 4b. So we must have b = 5 or 7. If b = 5, then we find c = 15, which gives a solution. If b = 7, then we find c = 23/3 which is not a solution.

The remaining case is n >= 3. If a = 2, we have n(bc - b - c + 1) = 2bc - 1, or (n - 2)bc + (n + 1) = nb + nc. But b ≥ 3, so (n - 2)bc ≥ (3n - 6)c ≥ 2nc for n ≥ 6, so we must have n = 3, 4 or 5. If n = 3, then bc + 4 = 3b + 3c. If b >= 6, then bc ≥ 6c > 3b + 3c, so b = 3, 4 or 5. Checking we find only b = 4 gives a solution: a = 2, b = 4, c = 8. If n = 4, then (n - 2)bc, nb and nc are all even, but (n + 1) is odd, so there is no solution. If n = 5, then 3bc + 6 = 5b + 5c. b = 3 gives c = 9/4, which is not a solution. b >= 4 gives 3bc > 10c > 5b + 5c, so there are no solutions.

If a = 3, we have 2n(bc - b - c + 1) = 3bc - 1, or (2n - 3)bc + (2n + 1) = 2nb + 2nc. But b ≥ 4, so (2n - 3)bc ≥ (8n - 12)c ≥ 4nc > 2nc + 2nb. So there are no solutions. Similarly, if a = 4, we have (3n - 4)bc + (3n + 1) = 3nb + 3nc. But b ≥ 4, so (3n - 4)bc ≥ (12n - 16)c > 6nc > 3nb + 3nc, so there are no solutions.

Problem A2

Find all functions f defined on the set of all real numbers with real values, such that f(x² + f(y)) = y + f(x)² for all x, y.

 

Solution

The first step is to establish that f(0) = 0. Putting x = y = 0, and f(0) = t, we get f(t) = t². Also, f(x²+t) = f(x)², and f(f(x)) = x + t². We now evaluate f(t²+f(1)²) two ways. First, it is f(f(1)² + f(t)) = t + f(f(1))² = t + (1 + t²)² = 1 + t + 2t² + t⁴. Second, it is f(t² + f(1 + t)) = 1 + t + f(t)² = 1 + t + t⁴. So t = 0, as required.

It follows immediately that f(f(x)) = x, and f(x²) = f(x)². Given any y, let z = f(y). Then y = f(z), so f(x² + y) = z + f(x)² = f(y) + f(x)². Now given any positive x, take z so that x = z². Then f(x + y) = f(z² + y) = f(y) + f(z)² = f(y) + f(z²) = f(x) + f(y). Putting y = -x, we get 0 = f(0) = f(x + -x) = f(x) + f(-x). Hence f(-x) = - f(x). It follows that f(x + y) = f(x) + f(y) and f(x - y) = f(x) - f(y) hold for all x, y.

Take any x. Let f(x) = y. If y > x, then let z = y - x. f(z) = f(y - x) = f(y) - f(x) = x - y = -z. If y < x, then let z = x - y and f(z) = f(x - y) = f(x) - f(y) = y - x. In either case we get some z > 0 with f(z) = -z < 0. But now take w so that w² = z, then f(z) = f(w²) = f(w)² >= 0. Contradiction. So we must have f(x) = x.

 

Problem A3

Consider 9 points in space, no 4 coplanar. Each pair of points is joined by a line segment which is colored either blue or red or left uncolored. Find the smallest value of n such that whenever exactly n edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

 

Solution

by Gerhard Wöginger

We show that for n = 32 we can find a coloring without a monochrome triangle. Take two squares R₁R₂R₃R₄ and B₁B₂B₃B₄. Leave the diagonals of each square uncolored, color the remaining edges of R red and the remaining edges of B blue. Color blue all the edges from the ninth point X to the red square, and red all the edges from X to the blue square. Color R_iB_j red if i and j have the same parity and blue otherwise.

Clearly X is not the vertex of a monochrome square, because if XY and XZ are the same color then, YZ is either uncolored or the opposite color. There is no triangle within the red square or the blue square, and hence no monochrome triangle. It remains to consider triangles of the form R_iR_jB_k and B_iB_jR_k. But if i and j have the same parity, then R_iR_j is uncolored (and similarly B_iB_j), whereas if they have opposite parity, then R_iB_k and R_jB_k have opposite colors (and similarly B_iR_k and B_jR_k).

It remains to show that for n = 33 we can always find a monochrome triangle. There are three uncolored edges. Take a point on each of the uncolored edges. The edges between the remaining 6 points must all be colored. Take one of these, X. At least 3 of the 5 edges to X, say XA, XB, XC must be the same color (say red). If AB is also red, then XAB is monochrome. Similarly, for BC and CA. But if AB, BC and CA are all blue, then ABC is monochrome. 

Problem B1

L is a tangent to the circle C and M is a point on L. Find the locus of all points P such that there exist points Q and R on L equidistant from M with C the incircle of the triangle PQR.

 

Solution

Answer: Let X be the point where C meets L, let O be the center of C, let XO cut C gain at Z, and take Y on QR so that M be the midpoint of XY. Let L' be the line YZ. The locus is the open ray from Z along L' on the opposite side to Y.

mainly by Gerhard Wöginger, Technical University, Graz (I filled in a few details)

Let C' be the circle on the other side of QR to C which also touches the segment QR and the lines PQ and QR. Let C' touch QR at Y'. If we take an expansion (technically, homothecy) center P, factor PY'/PZ, then C goes to C', the tangent to C at Z goes to the line QR, and hence Z goes to Y'. But it is easy to show that QX = RY'.

We focus on the QORO'. Evidently X,Y' are the feet of the perpendiculars from O, O' respectively to QR. Also, OQO' = ORO' = 90. So QY'O' and OXQ are similar, and hence QY'/Y'O' = OX/XQ. Also RXO and O'Y'R are similar, so RX/XO = O'Y'/Y'R. Hence QY'·XQ = OX·O'Y' = RX·Y'R. Hence QX/RX = QX/(QR - QX) = RY'/(QR - RY') = RY'/QY'. Hence QX = RY'.

But QX = RY by construction (M is the midpoint of XY and QR), so Y = Y'. Hence P lies on the open ray as claimed. Conversely, if we take P on this ray, then by the same argument QX = RY. But M is the midpoint of XY, so M must also be the midpoint of QR, so the locus is the entire (open) ray.

Gerhard only found this after Theo Koupelis, University of Wisconsin, Marathon had already supplied the following analytic solution.

Take Cartesian coordinates with origin X, so that M is (a, 0) and O is (0, R). Let R be the point (b, 0) (we take a, b >= 0). Then Q is the point (2a - b, 0), and Y is (2a, 0). Let angle XRO be θ. Then tan θ = R/b and angle PRX = 2θ, so tan PRX = 2 tan θ/( 1 - tan²θ) = 2Rb/(b² - R²). Similarly, tan PQX = 2R(b - 2a)/( (b - 2a)² - R²).

If P has coordinates (A, B), then B/(b - A) = tan PRX, and B/(b - 2a + x) = tan PQX. So we have two simultaneous equations for A and B. Solving, and simplifying slightly, we find A = -2aR²/(b² - 2ab - R²), B = 2b(b - 2a)R/(b² - 2ab - R²). (*)

We may now check that B/(2a - A) = R/a, so P lies on YZ as claimed. So we have shown that the locus is a subset of the line YZ. But since b² - 2ab - R² maps the open interval (a + √(a² + R²), ∞) onto the open interval (0, ∞), (*) shows that we can obtain any value A in the open interval (-∞,0) by a suitable choice of b, and hence any point P on the ray (except its endpoint Z) by a suitable choice of R. 

Problem B2

Let S be a finite set of points in three-dimensional space. Let S_x, S_y, S_z be the sets consisting of the orthogonal projections of the points of S onto the yz-plane, zx-plane, xy-plane respectively. Prove that:

      |S|² <= |S_x| |S_y| |S_z|, where |A| denotes the number of points in the set A.

[The orthogonal projection of a point onto a plane is the foot of the perpendicular from the point to the plane.]

 

Solution

by Gerhard Wöginger

Induction on the number of different z-coordinates in S.

For 1, it is sufficient to note that S = S_z and |S| ≤ |S_x| |S_y|  (at most |S_x| points of S project onto each of the points of S_y).

In the general case, take a horizontal (constant z) plane dividing S into two non-empty parts T and U. Clearly, |S| = |T| + |U|, |S_x| = |T_x| + |U_x|, and |S_y| = |T_y| + |U_y|.
By induction, |S| = |T| + |U| ≤ (|T_x| |T_y| |T_z|)^1/2 + (|U_x| |U_y| |U_z|)^1/2. But |T_z|, |U_z| ≤ |S_z|, and for any positive a, b, c, d we have (a b)^1/2 + (c d)^1/2 ≤ ( (a + c) (b + d) )^1/2 (square!).
Hence |S| ≤ |S_z|^1/2( ( |T_x| + |U_x| ) ( |T_y| + |U_y| ) )^1/2 = ( |S_x| |S_y| |S_z| ) ^1/2.  

Problem B3

For each positive integer n, S(n) is defined as the greatest integer such that for every positive integer k ≤ S(n), n² can be written as the sum of k positive squares.

(a)  Prove that S(n) <= n² - 14 for each n ≥ 4.
(b)  Find an integer n such that S(n) = n² - 14.
(c)  Prove that there are infinitely many integers n such that S(n) = n² - 14.

 

Solution

(a)  Let N = n². Suppose we could express N as a sum of N - 13 squares. Let the number of 4s be a, the number of 9s be b and so on. Then we have 13 = 3a + 8b + 15c + ... . Hence c, d, ... must all be zero. But neither 13 nor 8 is a multiple of 3, so there are no solutions. Hence S(n) ≤ N - 14.

A little experimentation shows that the problem is getting started. Most squares cannot be expressed as a sum of two squares. For N = 13² = 169, we find: 169 = 9 + 4 + 4 + 152 1s, a sum of 155 = N - 14 squares. By grouping four 1s into a 4 repeatedly, we obtain all multiples of 3 plus 2 down to 41 (169 = 9 + 40 4s). Then grouping four 4s into a 16 gives us 38, 35, ... , 11 (169 = 10 16s + 9). Grouping four 16s into a 64 gives us 8 and 5. We obtain the last number congruent to 2 mod 3 by the decomposition: 169 = 12² + 5².

For the numbers congruent to 1 mod 3, we start with N - 15 = 154 squares: 169 = 5 4s + 149 1s. Grouping as before gives us all 3m + 1 down to 7: 169 = 64 + 64 + 16 + 16 + 4 + 4 + 1. We may use 169 = 10² + 8² + 2² + 1² for 4.

For multiples of 3, we start with N - 16 = 153 squares: 169 = 9 + 9 + 151 1s. Grouping as before gives us all multiples of 3 down to 9: 169 = 64 + 64 + 16 + 9 + 9 + 4 + 1 + 1 + 1. Finally, we may take 169 = 12² + 4² + 3² for 3 and split the 4² to get 169 = 12² + 3² + 2² + 2² + 2² + 2² for 6. That completes the demonstration that we can write 13² as a sum of k positive squares for all k <= S(13) = 13² - 14.

We now show how to use the expressions for 13² to derive further N. For any N, the grouping technique gives us the high k. Simply grouping 1s into 4s takes us down: from 9 + 4 + 4 + (N-17) 1s to (N-14)/4 + 6 < N/2 or below; from 4 + 4 + 4 + 4 + 4 + (N-20) 1s to (N-23)/4 + 8 < N/2 or below; from 9 + 9 + (N-18) 1s to (N-21)/4 + 5 < N/2 or below. So we can certainly get all k in the range (N/2 to N-14) by this approach. Now suppose that we already have a complete set of expressions for N₁ and for N₂ (where we may have N₁ = N₂). Consider N₃ = N₁N₂. Writing N₃ = N₁( an expression for N₂ as a sum of k squares) gives N₃ as a sum of 1 thru k₂ squares, where k₂ = N₂ - 14 squares (since N₁ is a square). Now express N₁ as a sum of two squares: n₁² + n₂². We have N₃ = n₁²(a sum of k₂ squares) + n₂²(a sum of k squares). This gives N₃ as a sum of k₂ + 1 thru 2k₂ squares. Continuing in this way gives N₃ as a sum of 1 thru k₁k₂ squares. But k_i = N_i - 14 > 2/3 N_i, so k₁k₂ > N₃/2. So when combined with the top down grouping we get a complete set of expressions for N₃.

This shows that there are infinitely many squares N with a complete set of expressions, for example we may take N = the squares of 13, 13², 13³, ...

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.