8th Canadian Mathematical Olympiad Problems 1976

8th Canadian Mathematical Olympiad Problems 1976

1.  Given four unequal weights in geometric progression, show how to find the heaviest weight using a balance twice.

2.  The real sequence x₀, x₁, x₂, ... is defined by x₀ = 1, x₁ = 2, n(n+1) x_n+1 = n(n-1) x_n - (n-2) x_n-1. Find x₀/x₁ + x₁x₂ + ... + x₅₀/x₅₁.

3.  n+2 students played a tournament. Each pair played each other once. A player scored 1 for a win, 1/2 for a draw and nil for a loss. Two students scored a total of 8 and the other players all had equal total scores. Find n.

4.  C lies on the segment AB. P is a variable point on the circle with diameter AB. Q lies on the line CP on the opposite side of C to P such that PC/CQ = AC/CB. Find the locus of Q.

5.  Show that a positive integer is a sum of two or more consecutive positive integers iff it is not a power of 2.

6.  The four points A, B, C, D in space are such that the angles ABC, BCD, CDA, DAB are all right angles. Show that the points are coplanar.

7.  p(x, y) is a symmetric polynomial with the factor (x - y). Show that (x - y)² is a factor.

8.  A graph has 9 points and 36 edges. Each edge is colored red or blue. Every triangle has a red edge. Show that there are four points with all edges between them red.

Solutions

Problem 1

Given four unequal weights in geometric progression, show how to find the heaviest weight using a balance twice.

Solution

Let the weights be b, bd, bd², bd³ with d > 1. Then d²(d - 1) > (d - 1), so bd³ + b > bd + bd². So if we test two weights against the other two then the heavier pair is sure to include the heaviest single weight (bd³). The second weighing determines which weight in the pair is heavier. 

Problem 2

The real sequence x₀, x₁, x₂, ... is defined by x₀ = 1, x₁ = 2, n(n+1) x_n+1 = n(n-1) x_n - (n-2) x_n-1. Find x₀/x₁ + x₁x₂ + ... + x₅₀/x₅₁.

Solution

We show by induction that x_n = 1/n! for n ≥ 2. We have 1·2 x₂ = 1·0. x₁ - (-1) x₀ = 1, so x₂ = 1/2 and the result is true for n = 2. We also have 2·3 x₃ = 2·1 x₂ - 0. x₁ = 1, so x₃= 1/6 and the result is true for n = 3.

Suppose it is true for n and n-1. Then n(n+1) x_n+1 = n(n-1)/n! - (n-2)/(n-1)! = 1/(n-2)! - 1/( (n-1) (n-3)! ) = (n-1 - (n-2) )/(n-1)! = 1/(n-1)!, so x_n+1 = 1/(n+1)! and the result is true for n+1.

Thus x₀/x₁ + x₁x₂ + ... + x₅₀/x₅₁ = 1/2 + 2/(1/2) + (1/2)/(1/6) + ... + (1/50!)/(1/51!) = 1/2 + 4 + 3 + 4 + 5 + ... + 51 = 3/2 + (1 + 2 + ... + 51) = 3/2 + 51.52/2 = 1327 1/2. 

Problem 3

n+2 students played a tournament. Each pair played each other once. A player scored 1 for a win, 1/2 for a draw and nil for a loss. Two students scored a total of 8 and the other players all had equal total scores. Find n.

Solution

There are (n+2)(n+1)/2 matches, so the total score is (n+2)(n+1)/2. Let the other players score k each. Then 8 + nk = (n+2)(n+1)/2, so n² - (2k-3) - 14 = 0. We know this equation has one root which is a positive integer. The product of the roots is -14, so the possibilities for the roots are: 1, -14; 2, -7; 7, -2; 14, -1. Hence the sum of the roots is -13, -5, 5, or 13 (respecively). Hence k = -5, -1, 4 or 8 (respectively). But k must be non-negative, so n = 7 or 14 is a necessary condition.

We need to check that these values can be achieved. Take n = 7, so there are 9 players in total. If every match is a draw, then every player draws 8 matches and scores 4, which satisfies the conditions. Take n = 14, so there are 16 players in total. Suppose one player loses to everyone, and all the other games end in a draw. Then the first player scores 0 and all the other players score 1 + 14/2 = 8. That also satisfies the conditions. 

Problem 4

C lies on the segment AB. P is a variable point on the circle with diameter AB. Q lies on the line CP on the opposite side of C to P such that PC/CQ = AC/CB. Find the locus of Q.

Solution

If C is the midpoint of AB, then the locus is obviously the same circle. So assume C is closer to A than B. Take B' on the line AB on the opposite side of A to B so that B'C = CB²/AC. We show that the locus is the circle diameter B'B.

Let this circle have center O'. Then BB' = BC + B'C = BC(1 + BC/AC) = AB. BC/AC. Hence B'O' = BO' = BO.BC/AC and O'C = BO' - BC = (BO/AC - 1)BC = OC.BC/AC. Now let Q' be the intersection of this circle with the ray PC. Then the triangles OCP and O'CQ' are similar (equal angle at C and OC/O'C = OP/O'Q). Hence PC/CQ = BC/AC. But there is only one point on the ray PC with the required ratio, so Q' = Q. 

Problem 5

Show that a positive integer is a sum of two or more consecutive positive integers iff it is not a power of 2.

Solution

(m+1) + (m+2) + ... + n = (n - m)(n + m + 1)/2 = N. If it is a sum of two or more, then n - m >= 2. If n - m = 2, then N = 2m + 3, which is odd. If n - m > 2, then N = a.b/2 where a and b are two integers greater than 2 of opposite parity, so N must have an odd factor, so it cannot be a power of 2.

Suppose N is not a power of 2. Then we can write 2N = ab with a, b of opposite parity and a, b > 1. We may assume a > b. If a = n + m + 1, b = n - m, then n = (a + b - 1)/2, m = (a - b - 1)/2. Since a and b are of opposite parity, n and m are integers. m is non-negative and n is positive. Also n - m ≥ 2. So we have N = (m+1) + (m+2) + ... + n as required.

[Examples: N = 12, then 2N = 3·8, so a = 8, b = 3, n = 5, m = 2 and 12 = 3 + 4 + 5; N = 24, then 2N = 3·16, so a = 16, b = 3, n = 9, m = 6, 24 = 7 + 8 + 9.] 

Problem 6

The four points A, B, C, D in space are such that the angles ABC, BCD, CDA, DAB are all right angles. Show that the points are coplanar.

Solution

Using Pythagoras: (1) AC² = AB² + BC², (2) BD² = BC² + CD², (3) CA² = CD² + DA², (4) DB² = DA² + AB². (1) + (3), (2) + (4) gives: 2 AC² = 2 BD², so AC = BD. So (1) and (2) give AB = CD, and (2) and (3) give BC = DA.

So triangles CBD and ADB are congruent. So ∠CBD = ∠ADB = 90^o - ∠ABD. So ∠CBD + ∠ABD = ∠CBA. Hence the line DB lies in the plane ABC, so the points are coplanar. 

Problem 7

p(x, y) is a symmetric polynomial with the factor (x - y). Show that (x - y)² is a factor.

Solution

We have p(x, y) = (x - y) q(x, y) for some polynomial q(x, y). But p(x, y) = p(y, x), so (x - y) q(x, y) = (y - x) q(y, x), or q(y, x) = - q(x, y). Hence q(x, x) = 0, so q(x, y) has a factor (x - y). 

Problem 8

A graph has 9 points and 36 edges. Each edge is colored red or blue. Every triangle has a red edge. Show that there are four points with all edges between them red.

Solution

We show first that any 5 points must have a red triangle.

Comment. This is just the result that the Ramsey number R(3, 4) <= 9. To see that 9 is best possible arrange 8 points in a circle and join each to its two neighbours and to the two points adjacent to its neighbours. Then every three points have an edge joining two of them, but there are no 4 points all joined. [Or if you prefer, color these edges red and join all other pairs with blue edges.]