4th Canadian Mathematical Olympiad Problems 1972

4th Canadian Mathematical Olympiad Problems 1972

1.  Three unit circles are arranged so that each touches the other two. Find the radii of the two circles which touch all three.

2.  x₁, x₂, ... , x_n are non-negative reals. Let s = ∑_i<j x_ix_j. Show that at least one of the x_i has square not exceeding 2s/(n² - n).

3.  Show that 10201 is composite in base n > 2. Show that 10101 is composite in any base.

4.  Show how to construct a convex quadrilateral ABCD given the lengths of each side and the fact that AB is parallel to CD.

5.  Show that there are no positive integers m, n such that m³ + 11³ = n³.

6.  Given any distinct real numbers x, y, show that we can find integers m, n such that mx + ny > 0 and nx + my < 0.

7.  Show that the roots of x² - 198x + 1 lie between 1/198 and 197.9949494949... . Hence show that √2 < 1.41421356 (where the digits 421356 repeat). Is it true that √2 < 1.41421356?

8.  X is a set with n elements. Show that we cannot find more than 2^n-1 subsets of X such that every pair of subsets has non-empty intersection.

9.  Given two pairs of parallel lines, find the locus of the point the sum of whose distances from the four lines is constant.

10.  Find the longest possible geometric progression in {100, 101, 102, ... , 1000}.

Solutions

Problem 1

Three unit circles are arranged so that each touches the other two. Find the radii of the two circles which touch all three.

Solution

The two circles have center at the center of the triangle, which is the centroid and hence a distance 2/3 √3 from the center of each of the unit circles. The two required radii are therefore 2/√3 ± 1.

Problem 2

x₁, x₂, ... , x_n are non-negative reals. Let s = ∑_i<j x_ix_j. Show that at least one of the x_i has square not exceeding 2s/(n² - n).

Solution

If not then each term of s exceeds 2s/(n²-n). But there are n(n-1)/2 terms.

Problem 3

Show that 10201 is composite in base n > 2. Show that 10101 is composite in any base.

Solution

Let the base be b, then 10201 = (b⁴ + 2b² + 1) = (b² + 1)² = 101². 10101 = (b⁴ + 2b² + 1) - b² = (b² + b + 1)(b² - b + 1). We have b > 1, so each factor is > 1.

Problem 4

Show how to construct a convex quadrilateral ABCD given the lengths of each side and the fact that AB is parallel to CD.

Solution

If AB = CD, then the quadrilateral is a parallelogram, so we must have BC = DA. In this case the construction is not unique. Draw AB, then any C on the circle center B radius BC. Then take the line through C parallel to AB to get D.

If AB > CD, then first construct a triangle ADX with sides AX = AB-CD and DX = BC. Then take B on the ray AX the required distance from A.

Problem 5

Show that there are no positive integers m, n such that m³ + 11³ = n³.

Solution

We have n³ = m³ mod 11. But we can easily check that 0³, 1³, 2³, ... , 10³ = 0, 10, 3, 6, 2, 7, 4, 9, 5, 8, 1 mod 11, so we must have n = m mod 11. Obviously we cannot have n = m, so we must have n = m+11k. But (m+11)³ - m³ = 3·11k·m² + 3·(11k)²m + (11k)³ > (11k)³ ≥ 11³. So there are no solutions.

Problem 6

Given any distinct real numbers x, y, show that we can find integers m, n such that mx + ny > 0 and nx + my < 0.

Solution

If x > y, take m = 1, n = -1, then mx + ny = x - y > 0 and nx + my = y - x < 0. Conversely, if x < y, take m = -1, n = 1, then mx + ny = y - x > 0, nx + my = x - y < 0.

Problem 7

Show that the roots of x² - 198x + 1 lie between 1/198 and 197.9949494949... . Hence show that √2 < 1.41421356 (where the digits 421356 repeat). Is it true that √2 < 1.41421356?

Solution

Let f(x) = x² - 198x + 1. Then f(1/198) = f(198 - 1/198) = 1/198². But f(x) = (x-99)² - 9800, so f(x) is decreasing for x < 99 and increasing for x > 99. Hence f(x) > 0 for x < 1/198 and x > 198 - 1/198 = 197.9949494949... .

The roots are x = 99 ± √9800 = 99 ± 70√2. Hence √2 < (99 - 1/198)/70 = 19601/13860 .(*)

1.41421356 = 1 + 41/100 + 421356/10⁸ (1 + 1/10⁶ + 1/10¹² + ... ) = 1 + 41/100 + 421356/(10⁸(1 - 1/10⁶) ) = 1 + 41/100 + 421356/99999900 = 19601/13860.

There may be a neater way, but multiplying out by hand to get the square is not that hard: 1.999 999 993 287 873 6 < 2. So 1.41421356 < √2.

Problem 8

X is a set with n elements. Show that we cannot find more than 2^n-1 subsets of X such that every pair of subsets has non-empty intersection.

Solution

There are 2ⁿ subsets. But they form 2^n-1 pairs: A, X-A and we can only have one member of each pair.

Problem 9

Given two pairs of parallel lines, find the locus of the point the sum of whose distances from the four lines is constant.

Solution

This is slightly messy. Suppose first the lines are all parallel. Suppose the distance between adjacent lines are a, b, c. Then any point between the inner two lines has the same sum a + 2b + c. For d < a + 2b + c, there are no points with sum d. For d > a + 2b + c, there is a line of points.

Now suppose the lines are not all parallel. Their points of intersection form a parallelogram ABCD. Suppose the distances between the opposite sides are a and b. Then any point inside the parallelogram has sum a + b. Clearly there are no points with smaller sum. For larger sums the locus is an octagon with opposite sides parallel and vertices on the parallel lines. Alternate sides lie inside a pair of parallel lines and are parallel to the other pair of parallel lines. A side not inside a pair of parallel lines forms an isosceles triangle with the point of intersection of the two lines containing its vertices.

[Note that all points on the base AB of an isosceles triangle C have the same sum of distances to the sides AC and BC. If the point X is on the base, then the sum is XA sin XAC + XB sin XBC = (XA + XB) sin XAC = AB sin A.]

Problem 10

Find the longest possible geometric progression in {100, 101, 102, ... , 1000}.

Solution

128, 192, 288, 432, 648, 972 has six terms and ratio 3/2. We show it is the best possible.

The ratio must be rational. Suppose it is h/k. If there are more than 6 terms, then the first term must be divisible by k⁶ and the last term must be divisible by h⁶. If k >= 3, then h > k, so h >= 4. But 4⁶ = 4096 > 1000, so the last term is not divisible by h⁶. So k < 3. We cannot have k = 1, because then the last term is at least h⁶ times the first term, which is impossible. So k = 2, h = 3. So the first term must be a multiple of 64. The smallest such is 128. But then we only get 6 terms.