23rd Canadian Mathematical Olympiad Problems 1991

23rd Canadian Mathematical Olympiad Problems 1991

1.  Show that there are infinitely many solutions in positive integers to a² + b⁵ = c³.

2.  Find the sum of all positive integers which have n 1s and n 0s when written in base 2.

3.  Show that the midpoints of all chords of a circle which pass through a fixed point lie on another circle.

4.  Can ten distinct numbers a₁, a₂, b₁, b₂, b₃, c₁, c₂, d₁, d₂, d₃ be chosen from {0, 1, 2, ... , 14}, so that the 14 differences |a₁ - b₁|, |a₁ - b₂|, |a₁ - b₃|, |a₂ - b₁|, |a₂ - b₂|, |a₂ - b₃|, |c₁ - d₁|, |c₁ - d₂|, |c₁ - d₃|, |c₂ - d₁|, |c₂ - d₂|, |c₂ - d₃|, |a₁ - c₁|, |a₂ - c₂| are all distinct?

5.  An equilateral triangle side n is divided into n² equilateral triangles side 1 by lines parallel to its sides. How many parallelograms can be formed from the small triangles? [For example, if n = 3, there are 15, nine composed of two small triangles and six of four.]

Solutions

Problem 1

Show that there are infinitely many solutions in positive integers to a² + b⁵ = c³.

Solution

We have 10² + 3⁵ = 7³. Hence (10n¹⁵)² + 3(n⁶)⁵ = (7n¹⁰)³ for all n.

Problem 2

Find the sum of all positive integers which have n 1s and n 0s when written in base 2.

Solution

The first digit must be 1. Then the remaining 2n-1 digits are subject only to the constraint that n are 0 and n-1 are 1. So there are (2n-1)!/(n! (n-1)! ) possibilities. There are (2n-2)!/( ( n! (n-2)! ) with a 1 in any given position (apart from the first). Thus the sum is (2n-1)!/(n! (n-1)! ) 2^2n-1 + (2n-2)!/( n! (n-2)! ) (1 + 2 + 2² + ... + 2^2n-2) = (2n-1)!/(n! (n-1)! ) 2^2n-1 + (2n-2)!/( n! (n-2)! ) (2^2n-1 - 1). For n = 1 the formula breaks down, but in that case the sum is obviously 2.

Problem 3

Show that the midpoints of all chords of a circle which pass through a fixed point lie on another circle.

Solution

Let the circle have center O and let the point be X. We have angle OMX = 90^o, so M lies on the circle diameter OX. [We are not asked to find the locus of M, simply to show that the locus is part of a circle. In fact, if X lies outside the circle, then the locus is the part of the circle diameter OX which lies inside the given circle. If X lies inside, then it is the complete circle diameter OX.]

Problem 4

Can ten distinct numbers a₁, a₂, b₁, b₂, b₃, c₁, c₂, d₁, d₂, d₃ be chosen from {0, 1, 2, ... , 14}, so that the 14 differences |a₁ - b₁|, |a₁ - b₂|, |a₁ - b₃|, |a₂ - b₁|, |a₂ - b₂|, |a₂ - b₃|, |c₁ - d₁|, |c₁ - d₂|, |c₁ - d₃|, |c₂ - d₁|, |c₂ - d₂|, |c₂ - d₃|, |a₁ - c₁|, |a₂ - c₂| are all distinct?

Solution

Answer: no.

We use a parity argument. There are 14 possible non-zero differences between numbers from the set {0, 1, 2, ... , 14}, namely 1, 2, ... , 14. Since the 14 differences are required to be all different, they must be 1, 2, ... , 14 (in some order). So exactly 7 of the differences must be odd. We show that this is impossible.

Suppose a₁ and a₂ have the same parity, and c₁ and c₂ have the same parity. Then either 0 or 2 of |a₁ - c₁|, |a₂ - c₂| are odd. But for each b_i, either both |a₁ - b_i|, |a₂ - b_i| are odd or neither are odd. So an even number of differences |a_i - b_j| are odd. Similarly, an even number of differences |c_i - d_j| are odd. So we must have an even number of odd differences. Contradiction.

Suppose a₁ and a₂ have opposite parity, and c₁ and c₂ have opposite parity. Again, an even number of |a_i - c_i| are odd. But now just one of |a₁ - b_i|, |a₂ - b_i| is odd, so three of |a_i - b_j| are odd, and similarly three of |c_i - d_j|, so an even number of odd differences in total. Contradiction.

Suppose a₁ and a₂ have the same parity, but c₁ and c₂ have opposite parity. Then just one of |a_i - c_i| is odd. But an even number of |a_i - b_j| are odd, whilst three of |c_i - d_j| are odd. So again we have an even number of odd differences in all. Contradiction. Similarly, if a₁ and a₂ have opposite parity, whilst c₁ and c₂ have the same parity.

Problem 5

An equilateral triangle side n is divided into n² equilateral triangles side 1 by lines parallel to its sides. How many parallelograms can be formed from the small triangles? [For example, if n = 3, there are 15, nine composed of two small triangles and six of four.]

Solution

Answer: (n+2)(n+1)n(n-1)/8 = 3 (n+2)C4.

The parallelogram must have angles 60^o, 120^o, 60^o, 120^o. The 60^o angles can be aligned in three ways (with one of the vertices of the triangle) and the number of parallelograms for each way is obviously equal. Suppose it is a_n (so that the total number of parallelograms is 3 a_n).

Let the big triangle be ABC. Let b_n be the number of parallelograms where one vertex of the parallelogram is A. Then we evidently have a_n = b_n + 2 b_n-1 + 3 b_n-2 + ... + (n-1) b₂. But it is easy to calculate b_n directly. Such a parallelogram is uniquely defined by the position of the vertex opposite to A. But that can have any position in the rows of vertices (of the small triangles) provided it is at least two rows below A and not at either end. Thus there are 1 + 2 + ... + n-1 = n(n-1)/2 possible positions for it. So b_n = n(n-1)/2 and b_n+1 - b_n = n. Hence a_n+1 - a_n = 1.n + 2(n-1) + 3(n-2) + ... + n.1 = n(1 + 2 + ... + n) - (1.2 + 2.3 + ... + (n-1)n) = n²(n+1)/2 - (n-1)n(n+1)/3 = n(n+1)(n+2)/6 = (n+2)C3. Now we claim that a_n = (n+2)C4. It is true for n = 2 (obviously a₂ = 1). So the result is a trivial induction, since (n+2)C4 + (n+2)C3 = (n+3)C4. Hence, finally, the total number of parallelograms is 3a_n = 3 (n+2)C4.