27th Canadian Mathematical Olympiad Problems 1995

27th Canadian Mathematical Olympiad Problems 1995

1.  Find g(1/1996) + g(2/1996) + g(3/1996) + ... + g(1995/1996) where g(x) = 9^x/(3 + 9^x).

2.  Show that x^xy^yz^z >= (xyz)^(x+y+z)/3 for positive reals x, y, z.

3.  A convex n-gon is divided into m quadrilaterals. Show that at most m - n/2 + 1 of the quadrilaterals have an angle exceeding 180^o.

4.  Show that for any n > 0 and k ≥ 0 we can find infinitely many solutions in positive integers to x₁³ + x₂³ + ... + x_n³ = y^3k+2.

5.  0 < k < 1 is a real number. Define f: [0, 1] → [0, 1] by f(x) = 0 for x ≤ k, 1 - (√(kx) + √( (1-k)(1-x) ) )² for x > k. Show that the sequence 1, f(1), f( f(1) ), f( f( f(1) ) ), ... eventually becomes zero.

Solutions

Problem 1

Find g(1/1996) + g(2/1996) + g(3/1996) + ... + g(1995/1996) where g(x) = 9^x/(3 + 9^x).

Solution

g(k) + g(1-k) = 1, so the sum is 997 + g(1/2) = 997 1/2. 

Problem 2

Show that x^xy^yz^z ≥ (xyz)^(x+y+z)/3 for positive reals x, y, z.

Solution

Assume x ≥ y ≥ z. Then x/z, x/y, y/z are all at least one and (x-z)/3, (x-y)/3, (y-z)/3 are all positive. Hence (x/z)^(x-z)/3, (x/y)^(x-y)/3, (y/z)^(y-z)/3 are all at least one. Hence their product is at least 1, which is the required relation. 

Problem 3

A convex n-gon is divided into m quadrilaterals. Show that at most m - n/2 + 1 of the quadrilaterals have an angle exceeding 180 degrees.

Solution

Suppose there are k vertices inside the n-gon. Then we have a total of n + k vertices, m + 1 faces and (4m + n)/2 edges. So using V + F = E + 2, we have n + k + m + 1 = 2m + n/2 + 1. Hence k = m - n/2 + 1. A quadrilateral can have at most one angle > 180^o. The vertex with that angle must be inside the n-gon (which is convex), so there are at most k quadrilaterals with an angle > 180^o. 

Problem 4

Show that for any n > 0 and k ≥ 0 we can find infinitely many solutions in positive integers to x₁³ + x₂³ + ... + x_n³ = y^3k+2.

Solution

It is sufficient to consider k = 0, for if N² is a sum of n positive cubes, then multiplying through by N^3k gives N^3k+2 as a sum of n positive cubes.

Moreover, it is sufficient to find a single example of N² as a sum of n positive cubes, for then multiplying through by any m⁶ gives a larger example.

But we have the familiar formula 1³ + 2³ + ... + n³ = ( n(n+1)/2 )². 

Problem 5

0 < k < 1 is a real number. Define f: [0, 1] → [0, 1] by f(x) = 0 for x ≤ k, 1 - (√(kx) + √( (1-k)(1-x) ) )² for x > k. Show that the sequence 1, f(1), f( f(1) ), f( f( f(1) ) ), ... eventually becomes zero.

Solution

We have f(1) = 1 - k. Also for x > k, f(x) = k + x - 2kx - 2 √(kx(1-k)(1-x) ). We have x > k, so (1-k) > (1-x) and kx(1-k)(1-x) > k²(1-x)² . Hence f(x) < k + x - 2kx - 2k(1-x) = x - k. So if x > k, then applying f reduces x by at least k. So applying it n times either reduces x below k or reduces it by at least nk. But k > 0, so applying f sufficiently many times must reduce x below k and thereafter it gives 0.