34th Canadian Mathematical Olympiad Problems 2002

34th Canadian Mathematical Olympiad Problems 2002

1.  What is the largest possible number of elements in a subset of {1, 2, 3, ... , 9} such that the sum of every pair (of distinct elements) in the subset is different?

2.  We say that the positive integer m satisfies condition X if every positive integer less than m is a sum of distinct divisors of m. Show that if m and n satisfy condition X, then so does mn.

3.  Show that x³/(yz) + y³/(zx) + z³/(xy) ≥ x + y + z for any positive reals x, y, z. When do we have equality?

4.  ABC is an equilateral triangle. C lies inside a circle center O through A and B. X and Y are points on the circle such that AB = BX and C lies on the chord XY. Show that CY = AO.

5.  Let X be the set of non-negative integers. Find all functions f: X → X such that x f(y) + y f(x) = (x + y) f(x² + y²) for all x, y.

Solutions

Problem 1

What is the largest possible number of elements in a subset of {1, 2, 3, ... , 9} such that the sum of every pair (of distinct elements) in the subset is different?

Solution

{1, 2, 3, 5, 8} has five elements and all pairs with a different sum. If there is a subset with 6 elements, then it has 15 pairs, each with sum at least 1 + 2 = 3 and at most 8 + 9 = 17. There are only 15 numbers at least 3 and at most 17, so each of them must be realised. But the only pair with sum 3 is 1,2 and the only pair with sum 17 is 8, 9 and then 1 + 9 = 2 + 8. So six elements is impossible.

Problem 2

We say that the positive integer m satisfies condition X if every positive integer less than m is a sum of distinct divisors of m. Show that if m and n satisfy condition X, then so does mn.

Solution

Suppose k < mn. Then k = am + b, where 0 ≤ a < n, 0 ≤ b < m. We may write a as a sum of distinct divisors of n. Hence am is a sum of distinct divisors of mn, each of them at least m. Also b is a sum of distinct divisors of m, each of them less than m. Hence k is a sum of distinct divisors of mn.

Problem 3

Show that x³/(yz) + y³/(zx) + z³/(xy) ≥ x + y + z for any positive reals x, y, z. When do we have equality?

Solution

(x⁴ + y⁴)/2 ≥ x²y² with equality iff x = y. Hence x⁴ + y⁴ + z⁴ ≥ x²y² + y²z² + z²x² with equality iff x = y = z.

(x²y² + y²z²)/2 ≥ xy²z. Hence x²y² + y²z² + z²x² ≥xyz(x + y + z). So x⁴ + y⁴ + z⁴ ≥ xyz(x + y + z) with equality iff x = y = z. Dividing by xyz gives the required result.

Problem 4

ABC is an equilateral triangle. C lies inside a circle center O through A and B. X and Y are points on the circle such that AB = BX and C lies on the chord XY. Show that CY equals AO.

Solution

Let O be the center of the circle. Chasing angles around ABXY we find that triangles AYC and AOB. Hence YC = OB.

[Let ∠OBA = x. Then ∠ABX = 2x, so ∠XBC = 2x - 60^o, so ∠BCX = ∠BXC = 120^o - x. Hence ∠ACY = 180^o - 60^o - (120^o - x) = x. ∠AYC = 180^o - ∠ABX = 180^o - 2x, so ∠YAC = x.]

Problem 5

Let X be the set of non-negative integers. Find all functions f: X → X such that x f(y) + y f(x) = (x + y) f(x² + y²) for all x, y.

Solution

Putting x = 0 we get y f(0) = y f(y²), so f(y²) = f(0) for all y. That strongly suggests f is constant. Obviously any constant function satisfies the condition.

Suppose f(x) < f(y) and neither x nor y is zero, then (x + y) f(x) < x f(y) + y f(x) < (x + y) f(y). Hence f(x) < f(x² + y²) < f(y). But that is impossible, because we could repeat the argument to get an infinite number of distinct values between f(x) and f(y). But we know that f(1) = f(0). Hence f(x) = f(1) for all x > 1. So f is constant.