28th Canadian Mathematical Olympiad Problems 1996

28th Canadian Mathematical Olympiad Problems 1996

1.  The roots of x³ - x - 1 = 0 are r, s, t. Find (1 + r)/(1 - r) + (1 + s)/(1 - s) + (1 + t)/(1 - t).

2.  Find all real solutions to the equations x = 4z²/(1 + 4z²), y = 4x²/(1 + 4x²), z = 4y²/(1 + 4y²).

3.  Let N be the number of permutations of 1, 2, 3, ... , 1996 in which 1 is fixed and each number differs from its neighbours by at most 2. Is N divisible by 3?

4.  In the triangle ABC, AB = AC and the bisector of angle B meets AC at E. If BC = BE + EA find angle A.

5.  Let x₁, x₂, ... , x_m be positive rationals with sum 1. What is the maximum and minimum value of n - [n x₁] - [n x₂] - ... - [n x_m] for positive integers n? 

Solutions

Problem 1

The roots of x³ - x - 1 = 0 are r, s, t. Find (1 + r)/(1 - r) + (1 + s)/(1 - s) + (1 + t)/(1 - t).

Solution

Put y = (1 + x)/(1 - x). Then x = (y - 1)/(y + 1), so y satisfies (y - 1)³ - (y - 1)(y + 1)² - (y + 1)³ = 0 or y³ + 7y² - y + 1 = 0. So the sum of the roots is -7. 

Problem 2

Find all real solutions to the equations x = 4z²/(1 + 4z²), y = 4x²/(1 + 4x²), z = 4y²/(1 + 4y²).

Solution

It is immediate from the equations given that 0 <= x, y, z < 1. Rearranging, we have 4z² = x/(1 - x), 4x² = y/(1 - y), 4y² = z/(1 - z). Multiplying gives (xyz)²(1 - x)(1 - y)(1 - z) = xyz/64. If x = 0, then from the first equation in the question, z = 0 and hence also y = 0. That is one solution. Otherwise we have xyz non-zero and hence x(1 - x) y(1 - y) z(1 - z) = 1/64. But x(1 - x) = 1/4 - (x - 1/2)² <= 1/4 with equality iff x = 1/2. Similarly for y and z, so the only other solution is x = y = z = 1/2. 

Problem 3

Let N be the number of permutations of 1, 2, 3, ... , 1996 in which 1 is fixed and each number differs from its neighbours by at most 2. Is N divisible by 3?

Solution

Let the number of permutations of 1, 2, ... , n with 1 fixed and each number differing from its neighbours by at most 2 be p(n). The first number must be 1, so the second number must be 2 or 3. If the second number is 2, then the number of permutations of 2, 3, ... , n with 2 fixed and each number differing from its neighbours by at most 2 is p(n-1). If the second number is 3, then the third number is 2, 4 or 5. If it is 2, then the fourth number must be 4. In that case, the number of permutations of 4, 5, ... , n with 4 fixed etc is p(n-3). So suppose it is not 2.

If we get two adjacent numbers (m m+1 or m m-1) then either all following numbers are greater or all following numbers are less. In the sequence 1, 3, ... we have missed out a smaller number, namely 2, so after the first even number we must go back to it. Hence after the first even number we cannot have any larger numbers. In other words, the only possibility for 1, 3, (not 2), ... is all the odd numbers in increasing sequence followed by all the even numbers in decreasing sequence, eg 1, 3, 5, 7, 9, 8, 6, 4, 2.

Thus we have established that p(n) = p(n-1) + p(n-3) + 1. Checking the first few values, we find p(1) = 1, p(2) = 1, p(3) = 2, p(4) = 4, p(5) = 6, p(6) = 9. So mod 3, we have:

n    1   2   3   4   5   6   7   8     9  10  11  12  13  14  15  16    17

p(n) 1   1   2   1   0   0   2   0     1   1   2   1   0   0   2   0     1

So there is a cycle of length 8. 1996 = 4 mod 8, so p(1996) = p(4) = 1 mod 3. 

Problem 4

In the triangle ABC, AB = AC and the bisector of angle B meets AC at E. If BC = BE + EA find angle A.

Solution

Take X on BC with BX = BE. Then CX = AE and so CX/CE = AE/CE = AB/BC = AC/BC. The the triangles BAC and CXE have a common angle C and the ratio of the two sides containing the angle the same. Hence they are similar. So XC = XE. Hence ∠BXE = 2 ∠C. But ∠C = 90^o - A/2 and ∠BXE = 90^o - B/4 (since BEX is isosceles) = 90^o - (90^o - A/2)/4. Solving gives A = 100^o. 

Problem 5

Let x₁, x₂, ... , x_m be positive rationals with sum 1. What is the maximum and minimum value of n - [n x₁] - [n x₂] - ... - [n x_m] for positive integers n?

Solution

[n x_i] ≤ n x_i and n(x₁ + ... + x_m) = n, so clearly the value cannot be less than 0. But we can achieve 0 by taking n to be (for example) the product of the denominators of the x_i. So the minimum value is 0.

If we take n to be one less than the product of the denominators, then every term has its absolute value reduced by 1, so we get a total value of m-1. But each of (n x_i - [n x_i]) is strictly less than one, so n - [n x₁] - ... - [n x_m] is less than m. It is an integer, so it is at most m - 1. Hence m - 1 is the maximum value.