25th Canadian Mathematical Olympiad Problems 1993

25th Canadian Mathematical Olympiad Problems 1993

1.  Show that there is a unique triangle such that (1) the sides and an altitude have lengths with are 4 consecutive integers, and (2) the foot of the altitude is an integral distance from each vertex.

2.  Show that the real number k is rational iff the sequence k, k + 1, k + 2, k + 3, ... contains three (distinct) terms which form a geometric progression.

3.  The medians from two vertices of a triangle are perpendicular, show that the sum of the cotangent of the angles at those vertices is at least 2/3.

4.  Several schools took part in a tournament. Each player played one match against each player from a different school and did not play anyone from the same school. The total number of boys taking part differed from the total number of girls by 1. The total number of matches with both players of the same sex differed by at most one from the total number of matches with players of opposite sex. What is the largest number of schools that could have sent an odd number of players to the tournament?

5.  A sequence of positive integers a₁, a₂, a₃, ... is defined as follows. a₁ = 1, a₂ = 3, a₃ = 2, a_4n = 2a_2n, a_4n+1 = 2a_2n + 1, a_4n+2 = 2a_2n+1 + 1, a_4n+3 = 2a_2n+1. Show that the sequence is a permutation of the positive integers. 

Solutions

Problem 1

Show that there is a unique triangle such that (1) the sides and an altitude have lengths with are 4 consecutive integers, and (2) the foot of the altitude is an integral distance from each vertex.

Solution

Answer: sides AB = 15, BC = 14, CA = 13, altitude AD = 12, BD = 9, DC= 5.

We need the familiar result that the sides of any right-angled triangle with integral sides may be written as (m²+n²)d, (m²-n²)d, 2mnd for integers m, n, d (see below).

Let the triangle be ABC, with altitude AD. AD differs in length from AB and AC by either 1, 2 or 3. So we have to find two right-angled triangles where the hypoteneuse differs from another side by 1, 2 or 3. Suppose AB = (m²+n²)d and AD =(m²-n²)d. If AB - AD = 1, then d = 1 and 2n² = 1, which is impossible. If AB - AD = 2, then we must have d = 1 and n = 1, so AB = m²+1, AD = m² - 1 and BD = 2m. Similarly, AB - AD = 3 is impossible.

If AD has the other form 2mnd, then AC - AD = 1 implies d = 1 and m = n+1, so AC = 2n²+2n+1, AD = 2n²+2n, CD = 2n+1. Similarly, AC - AD = 2 is impossible, and AC - AD = 3 implies d = 3 and m = n+1, so AC = 6n²+6n+3, AD = 6n²+6n, CD = 6n+3.

So we have to consider three possibilities. Either (1) AB = m²+1, AD = m²-1 = 2n²+2n, AC = m², BC = 2m+2n+1 = m²±2, or (2) AB = m²+1, AD = m²-1 = 6n²+6n, AC = m²+2, BC = 2m+6n+3 = m², or (3) AB = 2m²+2m+1, AD = 2m²+2m = 6n²+6n, AC = 6n²+6n+1, BC = 2m+1+6n+3 = 6n²+6n+2.

In case (1) we have from the relation for AC, 2n+1 = m²-2n, so the relation for BC gives 2m+m²-2n = m²±2, so m = n±1 and n⁴ ±2n²= 2n² + 2n giving n³-4n-2 = 0 or n³ = 2, which have no integral solutions.

In case (2) we have similarly m = 3n²-1, 3n³-4n-2 = 0, which has no integral solutions.

In case (3) we have m = 3n²-1 and 3n³-2n-1 = 0, which has the integral solution n = 1 and hence m = 2, giving the solution shown above.

The result about right-angled triangles can be proved as follows. Assume a, b, c are the sides of such a triangle with a² = b² + c². Take out the common factor d, so that a = Ad, b = Bd, c = Cd, with A, B, C having no common factor. We can assume that one of A and C are both odd. For if both are even, then B would also be even, contradicting our assumption that the three numbers have no common factor. If A is odd and C is even, then B must be odd and we can interchange B and C. Finally, we cannot have A even and B odd, for then C is odd, and hence A² is 2 mod 4, but a square cannot be 2 mod 4.

So A + C and A - C have a common factor 2. They cannot have a common factor 4, for then A and C would not be odd. But (A + C)(A - C) = B², so we must have A + C = 2m², A - C = 2n² for some relatively prime m, n. Hence A = m² + n², C = m² - n², B = 2mn and a = (m² + n²)d, B = 2mnd, C = (m² - n²)d, as claimed. 

Problem 2

Show that the real number k is rational iff the sequence k, k + 1, k + 2, k + 3, ... contains three (distinct) terms which form a geometric progression.

Solution

Suppose there are three such terms k + a, k + b, k + c. Then (k + b)² = (k + a)(k + c), so k(2b - a - c) = ac - b². If 2b - a - c = 0, then also ac - b² = 0, so b is both the AM and the GM of a and c. Hence a = c. But a, b, c are assumed to be unequal, so 2b - a - c is non-zero, hence k = (ac - b²)/(2b - a - c), which shows that k is rational.

Conversely, if k = m/n with m and n non-zero, then kmn = m², so (k + m)² = k(k + mn + 2m), which shows that the three terms k, k + m and k + mn + 2m are a GM of distinct terms. Finally if k = 0, the terms 1, 2 and 4 are a GM. 

Problem 3

The medians from two vertices of a triangle are perpendicular, show that the sum of the cotangent of the angles at those vertices is at least 2/3.

Solution

Let the triangle be ABC with medians AM and BN meeting at G. Angle A = angle NAG + angle BAG. Without loss of generality we may take AG = 2, GM = 1, GN = x, BG = 2x. So cot A = (cot NAG cot BAG - 1)/(cot NAG + cot BAG) = ( (2/x) (1/x) - 1)/(2/x + 1/x) = (2 - x²)/(3x). Similarly cot B = cot(ABG + MBG) = (2x.x - 1)/(2x + x). So cot A + cot B = (x² + 1)/(3x), which is at least 2/3 with equality iff x = 1. 

Problem 4

Several schools took part in a tournament. Each player played one match against each player from a different school and did not play anyone from the same school. The total number of boys taking part differed from the total number of girls by 1. The total number of matches with both players of the same sex differed by at most one from the total number of matches with players of opposite sex. What is the largest number of schools that could have sent an odd number of players to the tournament?

Solution

Answer: 3.

Let there be n schools. Suppose the ith school sends B_i boys and G_i girls. Let B = ∑ B_i and G = ∑ G_i. We are given that |B - G| = 1.

The number of same sex matches is 1/2 ∑ B_i(B - B_i) + 1/2 ∑ G_i(G - G_i) = (B² - ∑ B_i² + G² - ∑ G_i²). The number of opposite sex matches is ∑ B_i(G - G_i) = BG - ∑ B_iG_i. Thus we are given that B² - ∑ B_i² + G² - ∑ G_i² - 2BG + 2 ∑ B_iG_i = 0 or ±2. Hence (B - G)² - ∑(B_i - G_i)² = 0 or ±2. But (B - G)² = 1, so ∑(B_i - G_i)² = -1, 1 or 3. It cannot be negative, so it must be 1 or 3. Hence B_i = G_i except for 1 or 3 values of i, where |B_i - G_i| = 1. Thus the largest number of schools that can have B_i + G_i odd is 3. 

Problem 5

A sequence of positive integers a₁, a₂, a₃, ... is defined as follows. a₁ = 1, a₂ = 3, a₃ = 2, a_4n = 2a_2n, a_4n+1 = 2a_2n + 1, a_4n+2 = 2a_2n+1 + 1, a_4n+3 = 2a_2n+1. Show that the sequence is a permutation of the positive integers.

Solution

The first few terms are: a₁ = 1, a₂ = 3, a₃ = 2, a₄ = 6, a₅ = 7, a₆ = 5, a₇ = 4.

We claim that the terms a_m for m = 2ⁿ, 2ⁿ+1, 2ⁿ+2, ... , 2ⁿ⁺¹-1 are a permutation of 2ⁿ, 2ⁿ+1, 2ⁿ+2, ... , 2ⁿ⁺¹-1. By inspection this is true for n = 0, 1 and 2. Suppose it is true for n. Let S = {2ⁿ, 2ⁿ+1, ... , 2ⁿ⁺¹-1} and S' = {2ⁿ⁺¹, 2ⁿ⁺¹+1, ... , 2ⁿ⁺²}. As m runs through the numbers in S' which are 0 or 3 mod 4, [m/2] runs through the numbers in S and conversely as m runs through the even numbers in S, 2m runs through the numbers in S' which are 0 mod 4, and as m runs through the odd numbers in S, 2m+1 runs through the numbers in S' which are 3 mod 4. Thus the set {a_m: m belongs to S' and is 0 or 3 mod 4} = {k : k belongs to S' and is even}.

The odd numbers in S' are found by increasing all the even numbers in S' by 1. But a_4n+1 = a_4n+1 and a_4n+2 = a_4n+3+2, so the set {a_m: m belongs to S' and is 1 or 2 mod 4} is formed by increasing by 1 the members of the set {a_m: m belongs to S' and is 0 or 3 mod 4}. Hence {a_m: m belongs to S' and is 1 or 2 mod 4} = {k : k belongs to S' and is odd}. So we have established the result for n+1.