33rd Canadian Mathematical Olympiad Problems 2001

33rd Canadian Mathematical Olympiad Problems 2001

1.  A quadratic with integral coefficients has two distinct positive integers as roots, the sum of its coefficients is prime and it takes the value -55 for some integer. Show that one root is 2 and find the other root.

2.  The numbers -10, -9, -8, ... , 9, 10 are arranged in a line. A player places a token on the 0 and throws a fair coin 10 times. For each head the token is moved one place to the left and for each tail it is moved one place to the left. If we color one or more numbers black and the remainder white, we find that the chance of the token ending up on a black number is m/n with m + n = 2001. What is the largest possible total for the black numbers?

3.  The triangle ABC has AB and AC unequal. The angle bisector of A meets the perpendicular bisector of BC at X. The line joining the feet of the perpendiculars from X to AB and AC meets BC at D. Find BD/DC.

4.  A rectangular table has every entry a positive integer. n is a fixed positive integer. A move consists of either subtracting n from every element in a column or multiplying every element in a row by n. Find all n such that we can always end up with all zeros whatever the size or content of the starting table.

5.  A₀, A₁, A₂ lie on a circle radius 1 and A₁A₂ is not a diameter. The sequence A_n is defined by the statement that A_n is the circumcenter of A_n-1A_n-2A_n-3. Show that A₁, A₅, A₉, A₁₃, ... are collinear. Find all A₁A₂ for which A₁A₁₀₀₁/A₁₀₀₁A₂₀₀₁ is the 500th power of an integer. 

Solutions

Problem

A quadratic with integral coefficients has two distinct positive integers as roots, the sum of its coefficients is prime and it takes the value -55 for some integer. Show that one root is 2 and find the other root.

Solution

Let the roots be m and n and the leading coefficient k, then the quadratic is k(x² - (m + n)x + mn). The sum of its coefficients is k(m - 1)(n - 1). We are told this is prime, hence k = 1 and m = 2. So the quadratic is (x - 2)(x - n) with n > 2 an integer. We have (x - 2)(x - n) = -55 for some x. But the only factors of 55 are 1, 5, 11, 55, so x = 3, n = 58, or x = 7, n = 18. But n -1 is prime, so n = 18.

Problem 2

The numbers -10, -9, -8, ... , 9, 10 are arranged in a line. A player places a token on the 0 and throws a fair coin 10 times. For each head the token is moved one place to the left and for each tail it is moved one place to the left. If we color one or more numbers black and the remainder white, we find that the chance of the token ending up on a black number is m/n with m + n = 2001. What is the largest possible total for the black numbers?

Solution

The token must end on an even number, so clearly we color 1, 3, 5, 7, 9 black and -1, -3, -5, -7, -9 white. Let p(n) be the probability of the token ending up on n. Then p(10) = p(-10) = 1/1024, p(8) = p(-8) = 10/1024, p(6) = p(-6) = 45/1024, p(4) = p(-4) = 120/1024, p(2) = p(-2) = 210/1024, p(0) = 252/1024.

2001 = 3.23.29, so if m+n = 2001, then m = ka, n = kb, where a < b are coprime and k = 1, 3, 23, 29, 69, 78, 667 or 2001. b must be a power of 2, so the possibilities are: a/b = 0/1, 1/2, 7/16, 13/16, 5/64, 23/64, 155/512, 977/1024. Hence the probability must be h/1024 where h = 0, 512, 448, 832, 80, 368, 310 or 977.

We find that the only possibilities are 0, 512 = 252 + 120 + 120 + 10 + 10, 512 = 210 + 210 + 45 + 45 + 1 + 1, 310 = 210 + 45 + 45 + 10 = 977 = 252 + 210 + 210 + 120 + 120 + 45 + 10 + 10. These give sums (for the even numbers) of 0, 0, 0, 10, 6. So the best is 10, obtained by coloring black the even numbers 2, 6, -6, 8.

Thus we color -6, 1, 2, 3, 5, 6, 7, 8, 9 black and the rest white for a total of 45, giving a probability of 310/1024 = 155/512 = 465/1536, where 465 + 1536 = 2001.

Problem 3

The triangle ABC has AB and AC unequal. The angle bisector of A meets the perpendicular bisector of BC at X. The line joining the feet of the perpendiculars from X to AB and AC meets BC at D. Find BD/DC.

Solution

Let the perpendiculars from X to the lines AB, AC meet them at Z, Y respectively. Triangles XBZ, XYC are congruent because XB = XC (X lies on angle bisector), XZ = XY (X lies on perpendicular bisector) and ∠BZX = ∠CYX = 90^o. Hence BZ = CY. Also AZ = AY. By Ceva's theorem, (AZ/ZB) (BD/DC) (CY/YA) = 1. Hence BD/DC = 1.

Problem 4

A rectangular table has every entry a positive integer. n is a fixed positive integer. A move consists of either subtracting n from every element in a column or multiplying every element in a row by n. Find all n such that we can always end up with all zeros whatever the size or content of the starting table.

Solution

Neither type of move changes an entry mod n-1. So if n > 2, we can never zero entries which do not start as multiples of n-1. So we need only consider n = 1 and n = 2.

If n = 1, then only the column move achieves anything. But if we have at least two rows and a column in which not all the elements are equal, then we can never zero the column.

We show that if n = 2, then we can always zero the table. We zero one column at at time. Start by doubling any row with an odd entry, so that all entries become even. Now suppose the largest entry in the first column is 2m > 2, we can reduce it by doubling any 2s to 4 and then subtracting enough 2s to bring the smallest entry back to 2. We must eventually get all entries in the first column equal to 2. Now subtract 2, to zero the first column. Repeat for the other columns.

Problem 5

A₀, A₁, A₂ lie on a circle radius 1 and A₁A₂ is not a diameter. The sequence A_n is defined by the statement that A_n is the circumcenter of A_n-1A_n-2A_n-3. Show that A₁, A₅, A₉, A₁₃, ... are collinear. Find all A₁A₂ for which A₁A₁₀₀₁/A₁₀₀₁A₂₀₀₁ is the 500th power of an integer.

Solution

Let angle A₁A₃A₂ = x. Then A₁A₂ = 2A₁A₃ sin x/2 = 2 sin x/2. We have A_nA_n-2 = A_nA_n-1, since A_n-2 and A_n-1 lie on a circle center A_n. So by symmetry A₄ lies on the bisector of ∠A₁A₃A₂, so ∠A₄A₃A₂ = x/2. Hence ∠A₄A₂A₃ = x/2 and ∠A₂A₄A₃ = 180^o - x. Similarly A₅ lies on the bisector of ∠A₂A₄A₃, so ∠A₅A₄A₃ = 90^o - x/2. Hence ∠A₅A₃A₄ = 90^o - x/2 and ∠A₃A₅A₄ = x = ∠A₁A₃A₂. So triangles A₁A₃A₂ and A₃A₅A₄ are similar.

∠A₁A₃A₅ = ∠A₁A₃A₄ + A₄A₃A₅ = x/2 + 90^o - x/2 = 90^o. Also, 2A₃A₄ cos x/2 = A₁A₃ = 1, so A₃A₅/A₁A₃ = A₃A₄/A₁A₂ = 1/(2 sin x). Thus the triangle A₅A₇A₉ is similar to A₁A₃A₅ and rotated through 180^o. Hence A₁, A₅ and A₉ are collinear. Similarly, A_4n+1, A_4n+5 and A_4n+9 are collinear for any n and hence all of A₁, A₅, ... , A_4n+1, ... are collinear.

Put y = A₁A₃/A₃A₅ = 2 sin x. Then A₁A₁₀₀₁/A₁₀₀₁A₂₀₀₁ = y⁵⁰⁰ (because the structure A₁ A₃ A₅ ... A₁₀₀₁ is similar to A₁₀₀₁A₁₀₀₃ ... A₂₀₀₁ but larger by a factor (y²)²⁵⁰. So we want y to be an integer. Hence sin x = 1/2 or 1, so x = 30^o, 90^o or 150^o and A₁A₂ = 2 sin x/2 = 2 sin 15^o, 2 sin 45^o or 2 sin 75^o = (√3 - 1)/√2, √2 or (√3 + 1)/√2.