17th Canadian Mathematical Olympiad Problems 1985

17th Canadian Mathematical Olympiad Problems 1985

1.  A triangle has sides 6, 8, 10. Show that there is a unique line which bisects the area and the perimeter.

2.  Is there an integer which is doubled by moving its first digit to the end? [For example, 241 does not work because 412 is not 2 x 241.]

3.  A regular 1985-gon is inscribed in a circle (so each vertex lies on the circle). Another regular 1985-gon is circumcribed about the same circle (so that each side touches the circle). Show that the sum of the perimeters of the two polygons is at least twice the circumference of the circle. [Assume tan x >= x for 0 <= x < 90 deg.]

4.  Show that n! is divisible by 2^n-1 iff n is a power of 2.

5.  Define the real sequence x₁, x₂, x₃, ... by x₁ = k, where 1 < k < 2, and x_n+1 = x_n - x_n²/2 + 1. Show that |x_n - √2| < 1/2ⁿ for n > 2.

Solutions

Problem 1

A triangle has sides 6, 8, 10. Show that there is a unique line which bisects the area and the perimeter.

Solution

Let such a line cut the sides length 10 and 8, distances x and y respectively from their common vertex. Then the triangle with sides x and y has height 6x/10 and hence area 3xy/10. That must equal 12, so xy = 40. Also x + y = 12. But then (x - y)² = (x + y)² - 4xy = -16, so there are no such solutions.

If the line cuts the sides length 6 and 8, distances x and y from their common vertex, then we have xy = 24, x + y = 12. Hence x, y = 6 ± 2radic;3. But 6 + 2√3 > 6 and 8, so there are no such solutions.

The final possibility is that the line cuts the sides length 10 and 6, distances x and y respectively from their common vertex. Then xy = 30, x + y = 12, so x, y = 6 ± √6. The larger value exceeds 6, so we must have x = 6 + √6, y = 6 - √6, and the line is unique.

Problem 2

Is there an integer which is doubled by moving its first digit to the end? [For example, 241 does not work because 412 is not 2 x 241.]

Solution

Suppose such a number has first digit a, and n other digits. Then it is 10ⁿa + N for some N with n digits. Moving the first digit to the end transforms it to 10N + a, so we require 10N + a = 2(10ⁿa + N). Hence 8N = (2.10ⁿ - 1)a. Now 2.10ⁿ - 1 is odd, so 8 must divide a. Hence a = 8. So N = 2.10ⁿ - 1. But 2.10ⁿ - 1 > 10ⁿ and hence has n+1 digits. Contradiction. So there is no such number.

Problem 3

A regular 1985-gon is inscribed in a circle (so each vertex lies on the circle). Another regular 1985-gon is circumcribed about the same circle (so that each side touches the circle). Show that the sum of the perimeters of the two polygons is at least twice the circumference of the circle. [Assume tan x ≥ x for 0 ≤ x < 90^o.]

Solution

Let the circle have radius R and let a side of the inner polygon subtend an angle 2x at the center. Then the side has length 2R sin x. The side of the outer polygon is 2R tan x. So it is sufficient to show that sin x + tan x > 2x.

We have sin x = 2t/(1 + t²), tan x = 2t/(1 - t²), where t = tan(x/2). Hence sin x + tan x = 4t/(1 - t⁴) > 4t > 4 x/2 = 2x.

Problem 4

Show that n! is divisible by 2^n-1 iff n is a power of 2.

Solution

We claim that the highest power of 2 dividing n! is 2^n-b(n), where b(n) is the number of 1s in the binary expression for 2. This can easily be proved by induction. For n = 1 it is obvious. So suppose it is true for n. If n+1 is odd, then the highest power of 2 dividing (n+1)! is the same as that dividing n! and n+1 has the same binary digits as n except that the final 0 is replaced by 1, so n+1 - b(n+1) = n - b(n) and the result is true for n+1. Suppose n+1 is even and that 2^m is the highest power of 2 dividing n+1. Then the highest power dividing (n+1)! is m higher than that dividing n! . But n must have binary expansion ...011...1 (with m final 1s) and n+1 the expansion ...10...0 (with m final 0s). So b(n+1) = b(n) - m + 1. Hence n+1 - b(n+1) = n - b(n) + m. In other words, n+1 - b(n+1) is m larger than n - b(n). So the result is true for n+1. Hence the result is true for all n.

Finally, note that b(n) = 1 iff n is a power of 2.

Problem 5

Define the real sequence x₁, x₂, x₃, ... by x₁ = k, where 1 < k < 2, and x_n+1 = x_n - x_n²/2 + 1. Show that |x_n - √2| < 1/2ⁿ for n > 2.

Solution

f(x) = x - x²/2 + 1 = 3/2 - (x - 1)²/2, which is a strictly decreasing function over the range x = 1 to x = 2. Also, f(1) = 1.5, f(2) = 1 and f(1.5) = 11/8 = 1.375. Thus 1 < x₂ < 1.5 and 1.375 < x₃ < 1.5. We have √2 - 1/8 = 1.29, √2 + 1/8 = 1.53. So the required result is true for n = 3. We show that it is true for larger n by induction. Suppose it is true for n. Then x_n+1 < f(√2 - 1/2ⁿ) = √2 - 1/2ⁿ - (√2 - 1/2ⁿ)²/2 + 1 = √2 - 1/2ⁿ + (√2)/2ⁿ - 1/2²ⁿ⁺¹ < √2 + (√2 - 1)/2ⁿ < √2 + 1/2ⁿ⁺¹ (since √2 < 1.5). Similarly, x_n+1 > f(√2 + 1/2ⁿ) = √2 + 1/2ⁿ - (√2)/2ⁿ - 1/2²ⁿ⁺¹ = √2 - k/2ⁿ, where k = √2 + 1/2ⁿ⁺¹ - 1. Now n+1 >= 4 and √2 + 1/16 < 1.5, so k < 1/2. Hence x_n+1 > √2 - 1/2ⁿ⁺¹, which completes the induction.