30th Canadian Mathematical Olympiad Problems 1998

30th Canadian Mathematical Olympiad Problems 1998

1.  How many real x satisfy x = [x/2] + [x/3] + [x/5]?

2.  Find all real x equal to √(x - 1/x) + √(1 - 1/x).

3.  Show that if n > 1 is an integer then (1 + 1/3 + 1/5 + ... + 1/(2n-1) )/(n+1) > (1/2 + 1/4 + ... + 1/2n)/n.

4.  The triangle ABC has ∠A = 40^o and ∠B = 60^o. X is a point inside the triangle such that ∠XBA = 20^o and ∠XCA = 10^o. Show that AX is perpendicular to BC.

5.  Show that non-negative integers a <= b satisfy (a² + b²) = n²(ab + 1), where n is a positive integer, iff they are consecutive terms in the sequence a_k defined by a₀ = 0, a₁ = n, a_k+1 = n²a_k - a_k-1.

Solutions

Problem 1

How many real x satisfy x = [x/2] + [x/3] + [x/5]?

Solution

Answer: 30.

Put x = 30q + r, where q is an integer and 0 ≤ r < 30. Then x - [x/2] - [x/3] - [x/5] = -q + r - [r/2] - [r/3] - [r/5]. So x = [x/2] + [x/3] + [x/5] iff q = r - [r/2] - [r/3] - [r/5].

q, [r/2], [r/3] and [r/5] are all integers, so r must be an integer. There are 30 possible integral values of r (namely 0, 1, 2, ... , 29), so there is one solution x for each.

Problem 2

Find all real x equal to √(x - 1/x) + √(1 - 1/x).

Solution

Squaring are rearranging: x³ - x² - x - 2 = 2√(x³ - x² - x + 1). Squaring again, x²(x⁴ - 2x³ - x² - 2x + 1) = 0. Referring to the original equation, x = 0 is not a solution, so we must have x⁴ - 2x³ - x² - 2x + 1 = 0. Factorising (x² - x - 1)² = 0, so x = (1 + √5)/2 or (1 - √5)/2. But referring to the original equation, we must have x ≥ 1, so the only candidate is x = (1 + √5)/2.

With this value 1/x = (√5 - 1)/2, so x - 1/x = 1 and 1 - 1/x = ( (√5 - 1)/2)² and hence √(x - 1/x) + √(1 - 1/x) = x, as required.

Problem 3

Show that if n > 1 is an integer then (1 + 1/3 + 1/5 + ... + 1/(2n-1) )/(n+1) > (1/2 + 1/4 + ... + 1/2n)/n.

Solution

We have 1/2 + 1/3 + 1/5 + ... + 1/(2n-1) > 1/2 + 1/4 + 1/6 + ... + 1/2n). Also 1/2 + 1/2 + ... + 1/2 ≥ 1/2 + 1/4 + ... + 1/(2n), so 1/2 ≥ (1/2 + 1/4 + ... + 1/(2n) )/n. Adding, 1 + 1/3 + 1/5 + ... + 1/(2n-1) > (1/2 + 1/4 + ... + 1/(2n) )(1 + 1/n).

Problem 4

The triangle ABC has ∠A = 40^o and ∠B = 60^o. X is a point inside the triangle such that ∠XBA = 20^o and ∠XCA = 10^o. Show that AX is perpendicular to BC.

Solution

We use Ceva's theorem. (sin BAX/sin CAX) (sin ACX/sin BCX) (sin CBX/sin ABX) = 1. So, putting ∠BAX = x, we have sin x sin 10^o sin 40^o = sin(40^o-x) sin 70^o sin 20^o. But sin 40^o = 2 sin 20^o cos 20^o = 2 sin 20^o sin 70^o, so 2 sin x sin 10^o = sin(40^o-x). Putting x = 30^o + y, we get 2 sin(30^o+y) sin 10^o = sin(10^o-y). Expanding: cos y sin 10^o + √3 sin y sin 10^o = sin 10^o cos y - cos 10^o sin y, so sin y(cos 10^o + √3 cos 10^o) = 0. Hence sin y = 0, so y = 0^o and x = 30^o. So AX is perpendicular to BC (the angle between AX and BC is 180^o - 30^o - 60^o = 90^o).

Problem 5

Show that non-negative integers a ≤ b satisfy (a² + b²) = n²(ab + 1), where n is a positive integer, iff they are consecutive terms in the sequence a_k defined by a₀ = 0, a₁ = n, a_k+1 = n²a_k - a_k-1.

Solution

If n = 1, then the sequence is 0, 1, 1, 0, -1, -1, 0, 1, 1, ... . Thus the only consecutive non-negative terms a, b with a ≤ b are 0, 1 and 1, 1 both of which satisfy the equation.

Conversely suppose that a ≤ b is a solution for n = 1. Then a² + b² = ab + 1. If 1 < a, then 1 < a², ab ≤ b², so 1 + ab < a² + b². Contradiction. So a = 0 or 1. If a = 0, then b² = 1, so b = 1. If a = 1, then 1 + b² = b + 1, so b = 0 or 1, but b ≥ a = 1, so b = 1. Thus the only solutions are a = 0, b = 1, or a = 1, b = 1.

So assume n > 1. It is a trivial induction to show that a_k < a_k+1. Now it is an easy induction on k to show that consecutive terms a_k-1, a_k satisfy the equation. It is true for k = 1: (0² + n²) = n²(0.n + 1). Suppose it is true for k. Then we have a_k+1 + a_k-1 = n²a_k. Hence a_k+1² - a_k-1² = n²a_k(a_k+1 - a_k-1). Adding to a_k² + a_k-1² =n²(a_ka_k-1 + 1), we get a_k+1² + a_k² =n²(a_k+1a_k + 1), which completes the induction.

Now suppose that a ≤ b is any solution in non-negative integers of a² + b² = n²(ab + 1). The idea is to show that n²a - b, a is a smaller solution.

If a = b, then 2a² = n²(a² + 1) ≥ 4(a² + 1) > 2a². Contradiction. So a < b. If a = 0, then b² = n², so b = n. This solution belongs to the sequence. So assume a > 0.

If b > n²a, then b >= n²a + 1, so b² ≥ n²ab + b > n²ab + n²a ≥ n²(ab + 1), so a² + b² > n²(ab + 1). Contradiction. So n²a - b ≥ 0. If n²a ≥ a + b, then n²ab ≥ ab + b² > a² + b². Contradiction. So n²a - b < a. Finally, (n²a - b)² + a² = n⁴a² - 2n²ab + a² + b² = n²( a(n²a - b) + 1) + (a² + b² - n²(ab + 1) ), so if a, b is a solution, then so is n²a - b, a.

Thus if we start with any solution 0 < a ≤ b, we can derive a solution a' < a, where the relationship between a', a and b is the same as that between a_k-1, a_k and a_k+1. This process must terminate, so eventually we get a solution 0, c. But we have shown that this must be 0, n. So we must have been moving down the sequence a_k. Hence a, b must be consecutive terms in that sequence.