21st Canadian Mathematical Olympiad Problems 1989

21St Canadian Mathematical Olympiad Problems 1989

1.  How many permutations of 1, 2, 3, ... , n have each number larger than all the preceding numbers or smaller than all the preceding numbers?

2.  Each vertex of a right angle triangle of area 1 is reflected in the opposite side. What is the area of the triangle formed by the three reflected points?

3.  Tranform a number by taking the sum of its digits. Start with 1989¹⁹⁸⁹ and make four transformations. What is the result?

4.  There are five ladders. There are also some ropes. Each rope attaches a rung of one ladder to a rung of another ladder. No ladder has two ropes attached to the same rung. A monkey starts at the bottom of each ladder and climbs. Each time it reaches a rope, it traverses the rope to the other ladder and continues climbing up the other ladder. Show that each monkey eventually reaches the top of a different ladder.

5.  For every permutation a₁, a₂, ... , a_n of 1, 2, 4, 8, ... , 2^n-1 form the product of all n partial sums a₁ + a₂ + ... + a_k. Find the sum of the inverses of all these products.

Solutions

Problem 1

How many permutations of 1, 2, 3, ... , n have each number larger than all the preceding numbers or smaller than all the preceding numbers?

Solution

Answer: 2^n-1.

Let the number of permutations be a(n). The last number must be 1 or n, for if it is k with 1 < k < n, then it is preceded by 1 < k and by n > k. If the last number is n, then the preceding numbers satisfy the conditions for a permutation of 1, 2, ... , n-1. So there are a(n-1) permutations with last number n. Similarly, there are a(n-1) with last number 1. Hence a(n) = 2a(n-1). But a(2) = 2, so a(n) = 2^n-1. 

Problem 2

Each vertex of a right angle triangle of area 1 is reflected in the opposite side. What is the area of the triangle formed by the three reflected points?

Solution

Answer: 3.

Let the original triangle be ABC with angle B = 90^o. Let the reflection of A be A' and so on. Then ABA' and CBC' are straight lines and B is the midpoint of AA' and CC'. So C'A' is parallel to AC and of equal length. Also BB' is perpendicular to AC and to C'A'. Hence the altitude from B' to C'A' is three times the length of the altitude from B to AC. So the area of A'B'C' is three times that of ABC. 

Problem 3

Tranform a number by taking the sum of its digits. Start with 1989¹⁹⁸⁹ and make four transformations. What is the result?

Solution

Let f(n) be the sum of the digits of n. We have 1989¹⁹⁸⁹ < 10^4·1989, so f(n) < 4·1989·9 = 71604 < 99999, so f(f(n)) < 45. Hence f(f(f(n))) <= 12 and f(f(f(f(n)))) <= 9. But f(n) = n mod 9. Now 1989 = 0 mod 9, so 1989¹⁹⁸⁹ = 0 mod 9. Hence f(f(f(f(n)))) = 0 mod 9. Obviously f(n) > 0 if n > 0, so the result of the four tranformations must be 9. 

Problem 4

There are five ladders. There are also some ropes. Each rope attaches a rung of one ladder to a rung of another ladder. No ladder has two ropes attached to the same rung. A monkey starts at the bottom of each ladder and climbs. Each time it reaches a rope, it traverses the rope to the other ladder and continues climbing up the other ladder. Show that each monkey eventually reaches the top of a different ladder.

Solution

We have to show two separate things: that each monkey reaches the top of some ladder and that no two monkeys reach the top of the same ladder. Let us start with the second.

Let a section be the part of a ladder between two consecutive ropes. We claim that only one monkey can ever visit a given section. Suppose that was false. So suppose monkeys A and B both visit a particular section. Let S be the first section which A visits which is also visited by B. This cannot be the initial section of A's starting ladder, because B cannot get to that and it cannot be the initial section of any other ladder, because then A could not get to it. So it must be a section which has a rope R at its lowest point. A and B must both come along R to reach S, because if they came up the ladder from below they would have to go along R rather than S. But that means they must both have visited the section ending at the other end of the rope, contradicting the definition of S. That establishes the claim. In particular, only one monkey can visit the final section on a ladder, above the top rope, so at most one monkey can reach the top of any given ladder.

Similarly, we claim that a monkey can visit any given section at most once. Suppose otherwise. Let S be the first section that A visits that he later revisits. Let R be the rope at the start of S (as above, there must be such a rope). So on both visits A must have come along R, but that means he visited the section ending at the other end of the rope twice, contradicting the definition of S. That establishes the claim. But there are only a finite number of sections, so each monkey must eventually stop and that means it must reach the top of a ladder. 

Problem 5

For every permutation a₁, a₂, ... , a_n of 1, 2, 4, 8, ... , 2^n-1 form the product of all n partial sums a₁ + a₂ + ... + a_k. Find the sum of the inverses of all these products.

Solution

Answer: 1/2^N, where N = (n-1)n/2.

For example, we have:

n = 2: 1 2 partial sums 1 3 1/3

 2 1 partial sums 2 3 1/6

total 1/2

n = 3: 1 2 4 partial sums 1 3 7 1/21

 1 4 2 partial sums 1 5 7 1/35

 2 1 4 partial sums 2 3 7 1/42

 2 4 1 partial sums 2 6 7 1/84

 4 1 2 partial sums 4 5 7 1/140

 4 2 1 partial sums 4 6 7 1/168

total 1/8

We claim the more general result that if each a_i is a power of 2 with exponent b_i, then the sum of the inverses is 2^-B, where B is the sum of the b_i. We use induction on n. This is obvious for n = 1. Suppose it is true for < n. Let A be the sum of the a_k. The sum of the inverses over the permutations which have a_k last is (sum for the n-1 numbers excluding a_k) x 1/A = ( 1/2 to the power of (B - b_k) )/A. Hence the sum of all the inverses is (1/(A 2^B) x sum of 2 to the power of b_k = (1/(A 2^B) x sum of a_k = 1/2^B, which establishes the induction.