22nd Canadian Mathematical Olympiad Problems 1990

22nd Canadian Mathematical Olympiad Problems 1990

1.  A competition is played amongst n > 1 players over d days. Each day one player gets a score of 1, another a score of 2, and so on up to n. At the end of the competition each player has a total score of 26. Find all possible values for (n, d).

2.  n(n + 1)/2 distinct numbers are arranged at random into n rows. The first row has 1 number, the second has 2 numbers, the third has 3 numbers and so on. Find the probability that the largest number in each row is smaller than the largest number in each row with more numbers.

3.  The feet of the perpendiculars from the intersection point of the diagonals of a convex cyclic quadrilateral to the sides form a quadrilateral q. Show that the sum of the lengths of each pair of opposite sides of q is equal.

4.  A particle can travel at a speed of 2 meters/sec along the x-axis and 1 meter/sec elsewhere. Starting at the origin, which regions of the plane can the particle reach within 1 second.

5.  N is the positive integers, R is the reals. The function f : N → R satisfies f(1) = 1, f(2) = 2 and f(n+2) = f(n+2 - f(n+1) ) + f(n+1 - f(n) ). Show that 0 ≤ f(n+1) - f(n) ≤ 1. Find all n for which f(n) = 1025.

Solutions

Problem 1

A competition is played amongst n > 1 players over d days. Each day one player gets a score of 1, another a score of 2, and so on up to n. At the end of the competition each player has a total score of 26. Find all possible values for (n, d).

Answer

(n, d) = (3, 13), (12, 4) or (25, 2)

Solution

Each day n(n+1)/2 points are scored, so dn(n+1)/2 over the whole competition. This equals 26n, so d(n+1) = 52. So d = 1, 2, 4, 13 or 52. But d = 1 does not work, because one player scores 1 not 26. d = 2 (n = 25) does work: one player scores 1, 25 on successive days, the next 2, 24, the third 3, 23 and so on. d = 4 (n = 12) also works. For example, the players' scores could be:

day 1  1   2   3   4   5   6   7   8   9  10  11  12

day 2 12  11  10   9   8   7   6   5   4   3   2   1

day 3  1   2   3   4   5   6   7   8   9  10  11  12

day 4 12  11  10   9   8   7   6   5   4   3   2   1

d = 13 (n = 3) also works (in the first three days each players scores 6, then in each 5 successive pairs of days he scores 4):

day  1   2   3   4   5   6   7   8   9  10  11  12  13

player 1  1   2   3   1   3   1   3   1   3   1   3   1   3

player 2  2   3   1   3   1   3   1   3   1   3   1   3   1

player 3  3   1   2   2   2   2   2   2   2   2   2   2   2

d = 52 does not work, because there are no players! 

Problem 2

n(n + 1)/2 distinct numbers are arranged at random into n rows. The first row has 1 number, the second has 2 numbers, the third has 3 numbers and so on. Find the probability that the largest number in each row is smaller than the largest number in each row with more numbers.

Solution

Answer: 2ⁿ/(n+1)! .

Let the probability be p_n. The largest number must go into the last row. The probability of that happening is n/( n(n+1)/2 ) = 2/(n+1). It is then of no consequence what other numbers go in the last row. But the (n-1)n/2 numbers that go in the other n-1 rows must meet the criterion for n-1. The probability of that happening is p_n-1. Hence p_n = 2 p_n-1/(n+1). Also p₁ = 1. So by a trivial induction p_n = 2ⁿ/(n+1)! . 

Problem 3

The feet of the perpendiculars from the intersection point of the diagonals of a convex cyclic quadrilateral to the sides form a quadrilateral q. Show that the sum of the lengths of each pair of opposite sides of q is equal.

Solution

Let the quadrilateral be ABCD. Let the diagonals meet at X. Let the perpendiculars from X to AB, BC, CD, DA have feet at P, Q, R, S. Then ∠XPA = ∠XSA = 90^o. So XPSA is cyclic. ABCD is also cyclic and ∠PAS = ∠BAD, so PS/(diam XPSA) = BD/(diam ABCD). But the diameter of XPSA is AX. Let the diameter of ABCD be 2R, then PS/BD = AX/2R. Similarly, QR/BD = CX/2R, so (PS + QR)/BD = (AX + XC)/2R, or PS + QR = AC·BD/2R. Similarly, PQ + RS = BD·AC/2R. Hence result. 

Problem 4

A particle can travel at a speed of 2 meters/sec along the x-axis and 1 meter/sec elsewhere. Starting at the origin, which regions of the plane can the particle reach within 1 second.

Solution

Let O be the origin, B the point (2, 0), A the point (1/2, (√3)/2, and C the point (1, 0). We show that the region which can be reached in the first quadrant is any point in the triangle OAB and any point in the sector with center O and arc AC. The regions which can be reached in the other quadrants are obtained by reflecting this region in the two axes.

We consider first the best way of reaching the point P (a, b) in the first quadrant. Evidently it is to travel a distance (a - x) along the x-axis and then in a straight line to (a, b). So the time required is (a - x)/2 + (b² + x²)^1/2. We claim that this expression is at least a/2 + (b√3)/2 with equality iff x = b/√3. This is equivalent to showing that b² + x² ≥ (x/2 + (b√3)/2)² or 3x² - 2xb√3 + b² ≥ 0, or (x√3 - b)² >= 0, which is evidently true. Thus if a > b/√3, then one travels along the x-axis to X, where the angle BXP = 60^o and then directly to P. If angle POB > 60^o, then one goes directly from O to P.

If one goes to X and then P, with angle BXP = 60^o, then P must lie inside the triangle ABC. For take the point Q at the intersection of AB and XP. Triangles BXQ and BAO are similar, so XQ = AO·BX/OB =1·BX/2. Hence OX/2 + XQ = OB/2 = 1. In other words it takes exactly time 1 to reach Q. Hence P must lie on XQ. 

Problem 5

N is the positive integers, R is the reals. The function f : N → R satisfies f(1) = 1, f(2) = 2 and f(n+2) = f(n+2 - f(n+1) ) + f(n+1 - f(n) ). Show that 0 ≤ f(n+1) - f(n) <= 1. Find all n for which f(n) = 1025.

Solution

Calculating the first few values we find f(3) = 2, f(4) = 3, f(5) = f(6) = f(7) = 4, f(8) = 5, f(9) = f(10) = 6, f(11) = 7, f(12) = f(13) = f(14) = f(15) = 8, f(16) = 9. That suggests the pattern f(2ⁿ) = 2^n-1 + 1 and that the value m occurs k times, where 2^k-1 is the highest power of 2 dividing m.