14th Canadian Mathematical Olympiad Problems 1982

14th Canadian Mathematical Olympiad Problems 1982

1.  Given a quadrilateral ABCD and a point P, take A' so that PA' is parallel to AB and of equal length. Similarly take PB', PC', PD' equal and parallel to BC, CD, DA respectively. Show that the area of A'B'C'D' is twice that of ABCD.

2.  Show that the roots of x³ - x² - x - 1 are all distinct. If the roots are a, b, c show that (a¹⁹⁸² - b¹⁹⁸²)/(a - b) + (b¹⁹⁸² - c¹⁹⁸²)/(b - c) + (c¹⁹⁸² - a¹⁹⁸²)/(c - a) is an integer.

3.  What is the smallest number of points in n-dimensional space Rⁿ such that every point of Rⁿ is an irrational distance from at least one of the points.

4.  Show that the number of permutations of 1, 2, ... , n with no fixed points is one different from the number with exactly one fixed point.

5.  Let the altitudes of a tetrahedron ABCD be AA', BB', CC', DD' (so that A' lies in the plane BCD and similarly for B', C', D'). Take points A", B", C", D" on the rays AA', BB', CC', DD' respectively so that AA'·AA" = BB'·BB" = CC'·CC" = DD'·DD". Show that the centroid of A"B"C"D" is the same as the centroid of ABCD. 

Solutions

Problem 1

Given a quadrilateral ABCD and a point P, take A' so that PA' is parallel to AB and of equal length. Similarly take PB', PC', PD' equal and parallel to BC, CD, DA respectively. Show that the area of A'B'C'D' is twice that of ABCD.

Solution

Note that direction is important. PA' is parallel to AB, not antiparallel.

We have that area PA'B' = area ABC, area PB'C' = area BCD, area PC'D' = area CDA and area PD'A' = area DAB. In each case, the triangles are either congruent or have two sides the same lengths but the angles between them summing to 180^o (in which case their areas are the same). But area ABC + area CDA = area BCD + area DAB = area ABCD, so area A'B'C'D' = 2 x area ABCD. 

Problem 2

Show that the roots of x³ - x² - x - 1 are all distinct. If the roots are a, b, c show that (a¹⁹⁸² - b¹⁹⁸²)/(a - b) + (b¹⁹⁸² - c¹⁹⁸²)/(b - c) + (c¹⁹⁸² - a¹⁹⁸²)/(c - a) is an integer.

Solution

Put f(x) = x³ - x² - x - 1. We note that f(1) = -2, f(2) = 1, so there is a root between 1 and 2. The other two roots are complex. However, that does not help much for a proof.

But assume the roots are not all distinct, so we have a repeated root a and the third root b (which may also equal a). Then we have 2a + b = 1 (sum of roots), a² + 2ab = -1 (product of roots two at a time). Hence a² + 2a(1 - 2a) + 1 = 0 or -3a² + 2a + 1 = 0 or (3a + 1)(a - 1) = 0, so a = 1 or -1/3. But it is easy to check that these are not roots. So the roots must all be distinct.

Put h₁ = (a + b + c) = 1, h₂ = (ab + bc + ca) = -1, h₃ = abc = 1. Put k_n = (aⁿ - bⁿ)/(a - b) + (bⁿ - cⁿ)/(b - c) + (cⁿ - aⁿ)/(c - a). We wish to show that all k_n are integral.

We have k₁ = 3, k₂ = 2h₁, k₃ = 2h₁² - 3h², k₄ = 2h₁³ - 5h¹h² + 3h³. We claim that k_n+1 = h₁k_n - h₂k_n-1 + h₃k_n-2. This is proved by straightforward algebra. For example, the numerators of the terms with denominator (a - b) on the rhs are (a + b + c)(aⁿ - bⁿ) - (ab + bc + ca)(a^n-1 - b^n-1) + abc(a^n-2 - b^n-2) = aⁿ⁺¹ - abⁿ + aⁿb - bⁿ⁺¹ + aⁿc - bⁿc - aⁿb + abⁿ - a^n-1bc + bⁿc - aⁿc + ab^n-1c + a^n-1bc - ab^n-1c = aⁿ⁺¹ - bⁿ⁺¹. Thus the desired conclusion (that all k_n are integral follows by a trivial induction).

Comment. Note that the recurrence relation is the same as that for the powers:

Put A = a + b + c, B = ab + bc + ca, C = abc, xn = an + bn + cn

x1 = A

x2 = A2 - 2B

x3 = A3 - 3AB + 3C

x4 = A4 - 4A2B + 4AC + 2B2

xn+1 = Axn - Bxn-1 + Cxn-2

Problem 
3

What is the smallest number of points in n-dimensional space Rⁿ such that every point of Rⁿ is an irrational distance from at least one of the points.

Solution

Answer: n = 1 number is 2. For n > 1, number is 3.

The result for n = 1 is obvious. The result for n > 1 follows from the fact that we can choose three collinear points A, M, B such that the distance of any point P from one of them is irrational. We can take a plane through P and A, M, B so the number of dimensions is unimportant.

Let M be the midpoint of AB. Let PA = a, PB = b, PM = d, and AM = c. Let angle PMA = x. Then the cosine rule gives a² = d² + c² - 2dc cos x, b² = d² + c² + 2dc cos x. So, adding, a² + b² = 2d² + 2c², so d² = (a² + b²)/2 - c². Thus if we take c² to be irrational, then if a and b are rational, d², and hence d, is irrational. 

Problem 4

Show that the number of permutations of 1, 2, ... , n with no fixed points is one different from the number with exactly one fixed point.

Solution

Put a(n) be the number of permutations with just 1 fixed point and d(n) the number with no fixed points. We find that:

n 2    3    4

a(n) 0    3    8

d(n) 1    2    9

Evidently we wish to show that d(n) = a(n) + (-1)ⁿ (*). Note that it is almost obvious that a(n) = n d(n-1). [If k is the fixed point, then the other n-1 points have no fixed points.] There are two basic approaches. One is to establish the well-known formula d(n) = n! - n!/1! + n!/2! - n!/3! + ... + (-1)ⁿn!/n! . The other is to try to find a direct combinatorial argument for (*). The latter is not promising, because it is well-known that the direct combinatorial argument for d(n) = n d(n-1) + (-1)ⁿ is hard.

The formula is a simple application of the principle of inclusion and exclusion. Let c_S(n) be the number of permutations of 1, 2, ... , n which fix the points in the subset S. Evidently c_S(n) = (n - |S| )! (where nCk is the binomial coefficient), since we can permute the remaining n-|S| points arbitrarily.

Hence the number of permutations with no fixed points is n! - nC1 (n-1)! + nC2 (n-2)! - ... + (-1)ⁿ nCn 0! = n! (1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n! ). The required result now follows immediately, for a(n) = n d(n-1) = n (n-1)! (1 - 1/1! + 1/2! - ... + (-1)^n-1/(n-1)! ) = d(n) - (-1)ⁿ.

Thanks to Jacob Tsimerman for pointing out an error in the original proof.

The principle of inclusion and exclusion is as follows. Suppose we have N objects each of which may have one or more of the properties a, b, c, ... . Let N_a be the number with property a, N_ab the number with properties a and b, and so on. Then the number with none of these properties is N - N_a - N_b - ... + N_ab + N_ac + ... - N_abc - ... ± N_abc....

Problem 5

Let the altitudes of a tetrahedron ABCD be AA', BB', CC', DD' (so that A' lies in the plane BCD and similarly for B', C', D'). Take points A", B", C", D" on the rays AA', BB', CC', DD' respectively so that AA'·AA" = BB'·BB" = CC'·CC" = DD'·DD". Show that the centroid of A"B"C"D" is the same as the centroid of ABCD.

Solution

Take vectors with origin at the centroid O of ABCD. Put A for the vector OA etc. The vector (C - B) x (D - B) has direction along AA" and magnitude equal to the area of BCD or the volume of ABCD divided by that length AA'. Hence the vector AA" is k (C - B) x (D - B) of some k and the vector BB" is k (A - C) x (D - C) with the same k. Similarly, CC" is k (A - D) x (B - D) and DD" is k (C - A) x (B - A). [Note that care is needed to get the order of the factors correct in each case.] Thus we have to show that (C - B) x (D - B) + (A - C) x (D - C) + (A - D) x (B - D) + (C - A) x (B - A) = 0. Expanding, and remembering that X x X = 0 and Y x X = -X x Y, we get C x D - C x B - B x D + A x D - A x C - C x D + A x B - A x D - D x B + C x B - C x A - A x B = 0. Hence the centroid of A"B"C"D" is also O.