35th Canadian Mathematical Olympiad Problems 2003

35th Canadian Mathematical Olympiad Problems 2003

1.  The angle between the hour and minute hands of a standard 12-hour clock is exactly 1^o. The time is an integral number n of minutes after noon (where 0 < n < 720). Find the possible values of n.

2.  What are the last three digits of 2003^N, where N = 2002²⁰⁰¹.

3.  Find all positive real solutions to x³ + y³ + z³ = x + y + z, x² + y² + z² = xyz.

4.  Three fixed circles pass through the points A and B. X is a variable point on the first circle different from A and B. The line AX meets the other two circles at Y and Z (with Y between X and Z). Show that XY/YZ is independent of the position of X.

5.  S is any set of n distinct points in the plane. The shortest distance between two points of S is d. Show that there is a subset of at least n/7 points such that each pair is at least a distance d√3 apart.

Solutions

Problem 1

The angle between the hour and minute hands of a standard 12-hour clock is exactly 1^o. The time is an integral number n of minutes after noon (where 0 < n < 720). Find the possible values of n.

Solution

The angles of the minute, hour hands are 6n, n/2 degrees, so we want 11n/2 = 360k +- 1 for some k. Hence n = 65k + (5k +- 2)/11. Since 0 < n < 720, we have 0 < k < 11. Also 5k = 2 or -2 mod 11, so k = 4 or 7, giving n = 262 or 458.

Problem 2

What are the last three digits of 2003^N, where N = 2002²⁰⁰¹.

Answer

241

Solution

3² = 10 - 1, so 3⁴ⁿ = (10 - 1)²ⁿ = 1 - 20n + 100n(2n-1) = 1 - 120n + 200n² mod 1000. Hence 3¹⁰⁰ = 1 mod 1000. Now 2002²⁰⁰¹ = 2²⁰⁰¹ mod 100, and 2¹⁰ = -1 mod 25, so 2¹⁹⁹⁹ = (-1)¹⁹⁹ 512 = -12 = 13 mod 25. Hence 2²⁰⁰¹ = 4·13 = 52 mod 100. So 2003^N = 3⁵² mod 1000.

But, using the formula above, 3⁵² = 1 - 120·13 + 200·13² = 1 - 560 + 800 = 241 mod 1000.

Problem 3

Find all positive real solutions to x³ + y³ + z³ = x + y + z, x² + y² + z² = xyz.

Solution

We have xyz = x² + y² + z² > y² + z² ≥ 2yz. Hence x > 2. Hence x³ > x. Similarly, y³ > y and z³ > z. Contradiction. So there are no solutions.

Problem 4

Three fixed circles pass through the points A and B. X is a variable point on the first circle different from A and B. The line AX meets the other two circles at Y and Z (with Y between X and Z). Show that XY/YZ is independent of the position of X.

Solution

Designate one side of the line AB the left side and the other the right side as shown. Take a point T on the right side of the line XYZ which is to the right of X, Y, Z. Then irrespective of whether X is on the right or left side of AB, the angle BXT remains a fixed quantity independent of the position of X. Since the locus of X is a circle, this is obvious whilst X stays on the same side of AB. If X crosses AB from left to right, then ∠BXA changes to 180^o - (the previous) ∠BXA. But at the same time ∠BXT changes from ∠BXA to 180^o - ∠BXA, so ∠BXT remains unchanged. Similarly for ∠BYT and ∠BZT.

It follows that as X varies the points X, Y, Z, T remain in the same order along the line. Take this order to be X, Y, Z. Then the angles in the triangle BXY remain the same. (Put ∠BXT = x, ∠BYT = y, ∠BZT = z, then ∠BYX = 180^o - y, and ∠XBY = y - x). Similarly, the angles in the triangle BYZ remain the same. Only the scale varies. Hence the ratio XY/YZ remains the same.

Comment. This is one of those questions which is obvious, but hard to get right. The whole difficulty is making sure that the argument still works whatever the configuration. Obviously, an alternative approach is to examine the numerous different cases.

Problem 5

S is any set of n distinct points in the plane. The shortest distance between two points of S is d. Show that there is a subset of at least n/7 points such that each pair is at least a distance d√3 apart.

Solution

Take a point A in S. Any point of S which lies south of A and less than √3 from A must lie outside or on the semicircle radius 1, center A (through P and S) and strictly inside the semicircle radius √3 center A (through Q and R). We can divide this region into 6 equal parts, such as PSRQ, where angle PAS = 30^o. Any two points in this region are less than the distance QS apart (since points on the boundary QS are not in the region). But if T is the foot of the perpendicular from S to AQ, then AT = √3/2, so T is the midpoint of AQ and SQ = SA = 1. Hence there is at most 1 point of S in each part, and at most 6 points south of A and a distance < √3 from it.

So start with the northernmost point A₁ of S, discard all points < √ 3 from it. Take A₂, the most northerly point (apart from A₁) of those remaining. Discard all points < √3 from it. Take A₃, the most northerly point (apart from A₁ and A₂) of those remaining. And so on. At each stage we discard less than 6 points. Let m = [n/7]. After picking m points A_i, we have discarded at most 6(m-1) points. If n = 7m, then we are home. If n > 7m, then we discard the points within √3 of A_m. We have now got m points A_i and we have discarded at most 6m points, so there are still at least n - m - 6m > 0 points south of A_m undiscarded, and we may pick A_m+1.