9th Canadian Mathematical Olympiad Problems 1977

9th Canadian Mathematical Olympiad Problems 1977

1.  Show that there are no positive integers m, n such that 4m(m+1) = n(n+1).

2.  X is a point inside a circle center O other than O. Which points P on the circle maximise ∠OPX?

3.  Find the smallest positive integer b for which 7 + 7b + 7b² is a fourth power.

4.  The product of two polynomials with integer coefficients has all its coefficients even, but at least one not divisible by 4. Show that one of the two polynomials has all its coefficients even and that the other has at least one odd coefficient.

5.  A right circular cone has base radius 1. The vertex is K. P is a point on the circumference of the base. The distance KP is 3. A particle travels from P around the cone and back by the shortest route. What is its minimum distance from K?

6.  The real sequence x₁, x₂, x₃, ... is defined by x₁ = 1 + k, x_n+1 = 1/x_n + k, where 0 < k < 1. Show that every term exceeds 1.

7.  Given m+1 equally spaced horizontal lines and n+1 equally spaced vertical lines forming a rectangular grid with (m+1)(n+1) nodes. Let f(m, n) be the number of paths from one corner to the opposite corner along the grid lines such that the path does not visit any node twice. Show that f(m, n) ≤ 2^mn.

Solutions

Problem 1

Show that there are no positive integers m, n such that 4m(m+1) = n(n+1).

Solution

If n > 2m, then n+1 ≥ 2m+2, so n(n+1) > 4m(m+1). If n < 2m, then n+1 <= 2m, so n(n+1) < 4m². So we must have n = 2m, but then n(n+1) = 2m(2m+1) = 4m(m + 1/2) which does not equal 4m(m+1). 

Problem 2

X is a point inside a circle center O other than O. Which points P on the circle maximise angle OPX?

Solution

Let the chord through X perpendicular to OX be AB. Extend AO to meet the circle again at C. Then O is the midpoint of AC and X is the midpoint of AB, so OX = BC/2. Now let P be any point on the major arc AB. Extend PO to meet the circle again ar R and extend PX to meet the circle again at Q. Take S on the ray XQ so that XS = XP. Then as before OX = RS/2. But ∠RQS = 90^o, so RS > RQ, so RQ < OX/2, so ∠OPX = ∠RPQ < ∠OAX. Thus A and B are the points which maximise the angle. 

Problem 3

Find the smallest positive integer b for which 7 + 7b + 7b² is a fourth power.

Solution

Let N = 7 + 7b + 7b². Then 7 divides N, so 7³ = 343 must divide 1 + b + b². 1 + 17 + 17² = 307 < 343, so b ≥ 18. In fact 1 + 18 + 18² = 343, so b = 18 is the smallest solution. 

Problem 4

The product of two polynomials with integer coefficients has all its coefficients even, but at least one not divisible by 4. Show that one of the two polynomials has all its coefficients even and that the other has at least one odd coefficient.

Solution

Let the polynomials be a_nxⁿ + ... + a₁x + a₀ and b_mx^m + ... + b₁x + b₀. Suppose each polynomial has at least one odd coefficient. Then let a_i be the odd coefficient with smallest i and b_j be the odd coefficient with smallest j. Then the coefficient of x^i+j in the product is a sum of terms a_hb_k with h + k = i + j. All terms except a_ib_j have either h > i or k > j, so all terms except a_ib_j are even. Hence the sum is odd. Contradiction. So we may suppose that all a_h are even. If all the b_k were also even, then every product term would be a multiple of 4, which is false, so at least one b_k is odd. 

Problem 5

A right circular cone has base radius 1. The vertex is K. P is a point on the circumference of the base. The distance KP is 3. A particle travels from P around the cone and back by the shortest route. What is its minimum distance from K?

Solution

The key is to cut the cone along KP and unroll it to give the sector of a circle. If the sector is bounded by KP and KP' and the arc PP', then evidently the particle travels along the straight line PP'. It is closest to K when it is at the midpoint M. The arc PP' has length 2π, so the ∠PKP' is 2π/3. Hence ∠KPP' = π/6, so KM = 3/2. 

Problem 6

The real sequence x₁, x₂, x₃, ... is defined by x₁ = 1 + k, x_n+1 = 1/x_n + k, where 0 < k < 1. Show that every term exceeds 1.

Solution

We show by induction that 1 < x_n < 1/(1 - k). It is true for n = 1. Suppose it is true for n. Then x_n+1 = 1/x_n + k > 1 - k + k = 1 and x_n+1 < 1 + k < 1/(1 - k). 

Problem 7

Given m+1 equally spaced horizontal lines and n+1 equally spaced vertical lines forming a rectangular grid with (m+1)(n+1) nodes. Let f(m, n) be the number of paths from one corner to the opposite corner along the grid lines such that the path does not visit any node twice. Show that f(m, n) ≤ 2^mn.

Solution

Induction on n. If n = 0, then there is just one path, so f(m, 0) = 1 ≤ 2^m. Suppose the result is true for n. Let the (n+1)th line of nodes be A', B', ... , X' and the nth line of nodes be A, B, ... , X with A adjacent to A' etc. Suppose that A' is the destination. We now count the paths with a given pattern of segments in the line A'X'. There are 2^m such patterns (each of m segments can be in or out). If the segments D'E'F' are in the pattern (but not C'D' or F'G'), then the path must include DD'E'F'F. In the case of a subpath of segments ending in A', such as A'B'C', the path must include A'B'C'C. In other words, we get a collection of subpaths each of which is three or (in one case) two sides of a rectangle. If we replace these subpaths by the other sides of these rectangles (DEF, A'ABC for the examples above), then we get a path for m, n. Moreover, this mapping is obviously injective. So there are at most 2^mn paths for any given pattern and hence at most 2^m2^mn = 2^m(n+1) paths in total.