6th Canadian Mathematical Olympiad Problems 1974

6th Canadian Mathematical Olympiad Problems 1974

1.  (1) given x = (1 + 1/n)ⁿ, y = (1 + 1/n)ⁿ⁺¹, show that x^y = y^x. (2) Show that 1² - 2² + 3² - 4² + ... + (-1)ⁿ⁺¹n² = (-1)ⁿ⁺¹(1 + 2 + ... + n).

2.  Given the points A (0, 1), B (0, 0), C (1, 0), D (2, 0), E (3, 0), F (3, 1). Show that angle FBE + angle FCE = angle FDE.

3.  All coefficients of the polynomial p(x) are non-negative and none exceed p(0). If p(x) has degree n, show that the coefficient of xⁿ⁺¹ in p(x)² is at most p(1)²/2.

4.  What is the maximum possible value for the sum of the absolute values of the differences between each pair of n non-negative real numbers which do not exceed 1?

5.  AB is a diameter of a circle. X is a point on the circle other than the midpoint of the arc AB. BX meets the tangent at A at P, and AX meets the tangent at B at Q. Show that the line PQ, the tangent at X and the line AB are concurrent.

6.  What is the largest integer n which cannot be represented as 8a + 15b with a and b non-negative integers?

7.  Bus A leaves the terminus every 20 minutes, it travels a distance 1 mile to a circular road of length 10 miles and goes clockwise around the road, and then back along the same road to to the terminus (a total distance of 12 miles). The journey takes 20 minutes and the bus travels at constant speed. Having reached the terminus it immediately repeats the journey. Bus B does the same except that it leaves the terminus 10 minutes after Bus A and travels the opposite way round the circular road. The time taken to pick up or set down passengers is negligible. A man wants to catch a bus a distance 0 < x < 12 miles from the terminus (along the route of Bus A). Let f(x) the maximum time his journey can take (waiting time plus journey time to the terminus). Find f(2) and f(4). Find the value of x for which f(x) is a maximum. Sketch f(x).

Solutions

Problem 1

(1) given x = (1 + 1/n)ⁿ, y = (1 + 1/n)ⁿ⁺¹, show that x^y = y^x. (2) Show that 1² - 2² + 3² - 4² + ... + (-1)ⁿ⁺¹n² = (-1)ⁿ⁺¹(1 + 2 + ... + n).

Solution

(1) Put k = (1 + 1/n). Then n kⁿ⁺¹ = (n+1) kⁿ or ny = (n+1)x. Hence k^ny = k^(n+1)x. Hence x^y = y^x.

(2) Induction. Obvious for n = 1. Suppose it is true or n. Then we need to show that (-1)ⁿ (n+1)² = (-1)ⁿ⁺²(1 + 2 + ... + n+1) - (-1)ⁿ⁺¹(1 + 2 + ... + n). In other words, (n+1)² = (1 + 2 + ... + n+1) + (1 + 2 + ... + n) (*). But 1 + 2 + ... + n = n(n+1)/2 (n/2 pairs of terms each with sum n+1) and 1 + 2 + ... + n+1 = (n+1)(n+2)/2, so the rhs of (*) is (n + n+2)(n+1)/2 = (n+1)². 

Problem 2

Given the points A (0, 1), B (0, 0), C (1, 0), D (2, 0), E (3, 0), F (3, 1). Show that ∠FBE + ∠FCE = ∠FDE.

Solution

∠FDE = ∠FBE + ∠BFD, so it is sufficient to prove that ∠FCE = ∠BFD. But cos FCE = 2/√5. We have BD² = BF² + EF² - 2BF.FE cos BFD, so cos BFD = 2/√5 also. 

Problem 3

All coefficients of the polynomial p(x) are non-negative and none exceed p(0). If p(x) has degree n, show that the coefficient of xⁿ⁺¹ in p(x)² is at most p(1)²/2.

Solution

Let p(x) be a_nxⁿ + a_n-1x^n-1 + ... + a₀. We are given that a_m ≤ a₀ for all m. The coefficient of xⁿ⁺¹ in p(x)² is k = a₁a_n + a₂a_n-1 + ... + a_na₁ ≤ a₀(a₁ + a₂ + ... + a_n). But p(1)² = sum of all terms a_ia_j. All the terms are non-negative, so if we drop the terms not involving a₀ we do not increase the total and get p(0)² ≥ 2a₀(a₁ + ... + a_n) ≥ 2k. 

Problem 4

What is the maximum possible value for the sum of the absolute values of the differences between each pair of n non-negative real numbers which do not exceed 1?

Solution

Let the numbers be x₁ >= x₂ >= ... >= x_n. Then the sum is (x₁ - x₂) + (x₁ - x₃) + ... + (x₁ - x_n) + (x₂ - x₃) + ... + (x₂ - x_n) + (x₃ - x₄) + ... + (x₃ - x_n) + ... + (x_n-1 - x_n) = (n-1) x₁ + (n-2) x₂ + (n-3) x₃ + ... + x_n-1 - (n-1) x_n - (n-2) x_n-1 - ... - x₂ = (n-1) x₁ + (n-3) x₂ + (n-5) x₃ + ... + (n - (2n-1)) x_n. Since all x_i are non-negative we maximise the sum by taking the x_i with non-positive coefficients to be zero and the x_i with positive coefficients to be 1. That gives the maximum M = (n-1) + (n-3) + (n-5) + ... . If n = 2m, then M = 1 + 3 + 5 + ... + 2m-1 = m². If n = 2m+1, then M = 2 + 4 + ... + 2m = m(m+1). We can combine that into a single formula as M = [n²/4]. 

Problem 5

AB is a diameter of a circle. X is a point on the circle other than the midpoint of the arc AB. BX meets the tangent at A at P, and AX meets the tangent at B at Q. Show that the line PQ, the tangent at X and the line AB are concurrent.

Solution

Let the lines AB and PQ meet at K. Let ∠XAB = x < 45^o, and take units so that AB = 1. Then QB = tan x, PA = cot x. So KB/(KB + 1) = KB/KA = QB/QA = tan²x, so KB = s²/(c² - s²), KA = c²/(c² - s²), where s = sin x, c = sin x. Form a right-angled triangle with hypoteneuse KX by dropping a perpendicular from X to AB. Then KX² = (KA - c²)² + (c s)² = KA²s² + KB²c² = s²c²/(c² - s²)² = KA·KB. Hence KX is the tangent at X. 

Problem 6

What is the largest integer n which cannot be represented as 8a + 15b with a and b non-negative integers?

Solution

Answer: 97 (=8.15 - 15 - 8).

98 = 6·15 + 8, 99 = 5·15 + 3·8, 100 = 4·15 + 5·8, 101 = 3·15 + 7·8, 102 = 2·15 + 9·8, 103 = 1·15 + 11·8, 104 = 13·8, 105 = 7·15. That gives 8 consecutive numbers. We can now get any larger number by adding a multiple of 8 to one of 98-105. To see that 97 cannot be expressed as 8a + 15b, note that b must be odd, but 97-15, 97-45, 97-75 are not multiples of 8.

For the general case of relatively prime positive m, n > 1, the largest number which cannot be written as ma + nb is mn - m - n. 

Problem 7

Bus A leaves the terminus every 20 minutes, it travels a distance 1 mile to a circular road of length 10 miles and goes clockwise around the road, and then back along the same road to to the terminus (a total distance of 12 miles). The journey takes 20 minutes and the bus travels at constant speed. Having reached the terminus it immediately repeats the journey. Bus B does the same except that it leaves the terminus 10 minutes after Bus A and travels the opposite way round the circular road. The time taken to pick up or set down passengers is negligible. A man wants to catch a bus a distance 0 < x < 12 miles from the terminus (along the route of Bus A). Let f(x) the maximum time his journey can take (waiting time plus journey time to the terminus). Find f(2) and f(4). Find the value of x for which f(x) is a maximum. Sketch f(x).

Solution

The bus takes 20 mins for 12 miles or 5/3 min/mile. For x <= 1, the best strategy is to wait up to 10 minutes for a returning bus, so f(x) = 10 + 5x/3. Similarly for 11 <= x <= 12, f(x) = f(12-x).

For 1 < x <= 6, the worst case is that he just misses the right bus, so that the wrong bus comes 10 minutes later and the right bus 10 minutes after that. So he can wait 10 minutes and then travel 12-x miles for a total time of 10 + 5(12 - x)/3 = 30 - 5x/3 or he can wait 20 minutes and then travel x miles for a total time of 20 + 5x/3. The first is better for x >= 3. So, summarising:

f(x) = 10 + 5x/3 for 0 ≤ x <= 1

       20 + 5x/3 for 1 < x <= 3

       30 - 5x/3 for 3 < x <= 6

       10 + 5x/3 for 6 < x <= 9

       40 - 5x/3 for 9 < x < 11

       30 - 5x/3 for x ≥ 11

f(2) = f(4) = 23 1/3. The maximum value of 25 minutes occurs at x = 3 and x = 9.