29th Canadian Mathematical Olympiad Problems 1997

29th Canadian Mathematical Olympiad Problems 1997

1.  How many pairs of positive integers have greatest common divisor 5! and least common multiple 50! ?

2.  A finite number of closed intervals of length 1 cover the interval [0, 50]. Show that we can find a subset of at least 25 intervals with every pair disjoint.

3.  Show that 1/44 > (1/2)(3/4)(5/6) ... (1997/1998) > 1/1999.

4.  Two opposite sides of a parallelogram subtend supplementary angles at a point inside the parallelogram. Show that the line joining the point to a vertex subtends equal angles at the two adjacent vertices.

5.  Find ∑_0≤k≤n (-1)^k nCk /(k³ + 9k² + 26k + 24), where nCk is the binomial coefficient n!/( k! (n-k)! ). 

Solutions

Problem 1

How many pairs of positive integers have greatest common divisor 5! and least common multiple 50! ?

Solution

Answer: 2¹⁴.

Let m, n satisfy the conditions. Clearly each must be divisible by 5!. Now 50!/5! is divisible by 15 distinct primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47. The precise power in each case does not matter. Suppose 11^a is the highest power of 11 dividing 50!/5!. Then mn must be divisible by 11^a. But we cannot have 11 dividing both m and n, otherwise we would increase their greatest common divisor. So either 11^a divides m, or it divides n. To avoid double-counting, we may assume that 47 divides m. Then for each of the other 14 primes we have two choices, giving 2¹⁴ possible numbers. [We cannot introduce any additional factors beyond those in 50!/5! or we would increase the lcm.] 

Problem 2

A finite number of closed intervals of length 1 cover the interval [0, 50]. Show that we can find a subset of at least 25 intervals with every pair disjoint.

Solution

There must be an interval with left-hand endpoint belonging to [n, n+1) for n = 0, 1, 2, ... , 49. For otherwise the collection would not cover some n+1-ε. Take such an interval for n = 0, 2, 4, ... , 48. That gives 25 disjoint intervals. 

Problem 3

Show that 1/44 > (1/2)(3/4)(5/6) ... (1997/1998) > 1/1999.

Solution

Put k = (1/2)(3/4)(5/6) ... (1997/1998). We have 1/2 < 2/3, 3/4 < 4/5 etc, so k < (2/3)(4/5)(6/7) ... (1998/1999). Hence k² < 1/1999 (the product telescopes). But 44² = 1936 < 1999, so 1/1999 < 1/44². Hence k < 1/44.

1/2 > 1/3, 3/4 > 3/5, 5/6 > 5/7 etc. So k > (1/3)(3/5) ... (1997/1999) = 1/1999. 

Problem 4

Two opposite sides of a parallelogram subtend supplementary angles at a point inside the parallelogram. Show that the line joining the point to a vertex subtends equal angles at the two adjacent vertices.

Solution

Let the parallelogram be ABCD and the point inside be X. Assume that ∠AXB + ∠CXD = 180^o. Translate the parallelogram a distance AD along the line AD so that D moves to A, C moves to B, A moves to A', B moves to B' and X moves to X'. Then O'AOB has opposite angles summing to 180^o, so it is cyclic. So ∠OAB = ∠OO'B. By construction OO' is parallel to CDD', so ∠OO'B = ∠B'BO' = ∠BCO, so BO subtends the same angles at A and C. Similarly, ∠OBC = ∠O'OB = ∠O'AB = ∠ODC, so OC subtends the same angles at B and D. 

Problem 5

Find ∑ (-1)^k nCk /(k³ + 9k² + 26k + 24), where the sum is taken from k = 0 to n and nCk is the binomial coefficient n!/( k! (n-k)! ).

Solution

We note first that ∑ (-1)^k nCk = (1 - 1)ⁿ = 0 and ∑ (-1)^k k nCk = 0. The latter is less obvious, but ∑ (-1)^k k nCk = ∑₁ⁿ (-1)^k n!/( (k-1)! (n-k)! ) = -n ∑ (-1)^h (n-1)! /( h! (n-1-h)! ) = -n (1 - 1)^n-1 = 0.

Now k³ + 9k² + 26k + 24 = (k + 2)(k + 3)(k + 4), so if the required sum is s, then s/( (n+1)(n+2)(n+3)(n+4) ) = ∑₀ⁿ (-1)^k (k + 1)   (n+4)C(k+4) = ∑₄ⁿ⁺⁴ (-1)^k (k-3)   (n+4)Ck. Now we have shown above that the sum from 0 to n+4 is zero. So s/( (n+1)(n+2)(n+3)(n+4) ) + terms k = 0, 1, 2, 3 is zero. The k = 0 term is -3, the k = 1 term is 2n+8, the k = 2 term is -(n² + 7n + 12)/2, and the k = 3 term is zero. Hence s/( (n+1)(n+2)(n+3)(n+4) ) = (n+1)(n+2)/2, so s = 1/(2(n+3)(n+4) ).