35th Canadian Mathematical Olympiad Problems 2003

35th Canadian Mathematical Olympiad Problems 2003

1.  The angle between the hour and minute hands of a standard 12-hour clock is exactly 1^o. The time is an integral number n of minutes after noon (where 0 < n < 720). Find the possible values of n.

2.  What are the last three digits of 2003^N, where N = 2002²⁰⁰¹.

3.  Find all positive real solutions to x³ + y³ + z³ = x + y + z, x² + y² + z² = xyz.

4.  Three fixed circles pass through the points A and B. X is a variable point on the first circle different from A and B. The line AX meets the other two circles at Y and Z (with Y between X and Z). Show that XY/YZ is independent of the position of X.

5.  S is any set of n distinct points in the plane. The shortest distance between two points of S is d. Show that there is a subset of at least n/7 points such that each pair is at least a distance d√3 apart.

Solutions

Problem 1

The angle between the hour and minute hands of a standard 12-hour clock is exactly 1^o. The time is an integral number n of minutes after noon (where 0 < n < 720). Find the possible values of n.

Solution

The angles of the minute, hour hands are 6n, n/2 degrees, so we want 11n/2 = 360k +- 1 for some k. Hence n = 65k + (5k +- 2)/11. Since 0 < n < 720, we have 0 < k < 11. Also 5k = 2 or -2 mod 11, so k = 4 or 7, giving n = 262 or 458.

Problem 2

What are the last three digits of 2003^N, where N = 2002²⁰⁰¹.

Answer

241

Solution

3² = 10 - 1, so 3⁴ⁿ = (10 - 1)²ⁿ = 1 - 20n + 100n(2n-1) = 1 - 120n + 200n² mod 1000. Hence 3¹⁰⁰ = 1 mod 1000. Now 2002²⁰⁰¹ = 2²⁰⁰¹ mod 100, and 2¹⁰ = -1 mod 25, so 2¹⁹⁹⁹ = (-1)¹⁹⁹ 512 = -12 = 13 mod 25. Hence 2²⁰⁰¹ = 4·13 = 52 mod 100. So 2003^N = 3⁵² mod 1000.

But, using the formula above, 3⁵² = 1 - 120·13 + 200·13² = 1 - 560 + 800 = 241 mod 1000.

Problem 3

Find all positive real solutions to x³ + y³ + z³ = x + y + z, x² + y² + z² = xyz.

Solution

We have xyz = x² + y² + z² > y² + z² ≥ 2yz. Hence x > 2. Hence x³ > x. Similarly, y³ > y and z³ > z. Contradiction. So there are no solutions.

Problem 4

Three fixed circles pass through the points A and B. X is a variable point on the first circle different from A and B. The line AX meets the other two circles at Y and Z (with Y between X and Z). Show that XY/YZ is independent of the position of X.

Solution

Designate one side of the line AB the left side and the other the right side as shown. Take a point T on the right side of the line XYZ which is to the right of X, Y, Z. Then irrespective of whether X is on the right or left side of AB, the angle BXT remains a fixed quantity independent of the position of X. Since the locus of X is a circle, this is obvious whilst X stays on the same side of AB. If X crosses AB from left to right, then ∠BXA changes to 180^o - (the previous) ∠BXA. But at the same time ∠BXT changes from ∠BXA to 180^o - ∠BXA, so ∠BXT remains unchanged. Similarly for ∠BYT and ∠BZT.

It follows that as X varies the points X, Y, Z, T remain in the same order along the line. Take this order to be X, Y, Z. Then the angles in the triangle BXY remain the same. (Put ∠BXT = x, ∠BYT = y, ∠BZT = z, then ∠BYX = 180^o - y, and ∠XBY = y - x). Similarly, the angles in the triangle BYZ remain the same. Only the scale varies. Hence the ratio XY/YZ remains the same.

Comment. This is one of those questions which is obvious, but hard to get right. The whole difficulty is making sure that the argument still works whatever the configuration. Obviously, an alternative approach is to examine the numerous different cases.

Problem 5

S is any set of n distinct points in the plane. The shortest distance between two points of S is d. Show that there is a subset of at least n/7 points such that each pair is at least a distance d√3 apart.

Solution

Take a point A in S. Any point of S which lies south of A and less than √3 from A must lie outside or on the semicircle radius 1, center A (through P and S) and strictly inside the semicircle radius √3 center A (through Q and R). We can divide this region into 6 equal parts, such as PSRQ, where angle PAS = 30^o. Any two points in this region are less than the distance QS apart (since points on the boundary QS are not in the region). But if T is the foot of the perpendicular from S to AQ, then AT = √3/2, so T is the midpoint of AQ and SQ = SA = 1. Hence there is at most 1 point of S in each part, and at most 6 points south of A and a distance < √3 from it.

So start with the northernmost point A₁ of S, discard all points < √ 3 from it. Take A₂, the most northerly point (apart from A₁) of those remaining. Discard all points < √3 from it. Take A₃, the most northerly point (apart from A₁ and A₂) of those remaining. And so on. At each stage we discard less than 6 points. Let m = [n/7]. After picking m points A_i, we have discarded at most 6(m-1) points. If n = 7m, then we are home. If n > 7m, then we discard the points within √3 of A_m. We have now got m points A_i and we have discarded at most 6m points, so there are still at least n - m - 6m > 0 points south of A_m undiscarded, and we may pick A_m+1.

[Read More...]

34th Canadian Mathematical Olympiad Problems 2002

34th Canadian Mathematical Olympiad Problems 2002

1.  What is the largest possible number of elements in a subset of {1, 2, 3, ... , 9} such that the sum of every pair (of distinct elements) in the subset is different?

2.  We say that the positive integer m satisfies condition X if every positive integer less than m is a sum of distinct divisors of m. Show that if m and n satisfy condition X, then so does mn.

3.  Show that x³/(yz) + y³/(zx) + z³/(xy) ≥ x + y + z for any positive reals x, y, z. When do we have equality?

4.  ABC is an equilateral triangle. C lies inside a circle center O through A and B. X and Y are points on the circle such that AB = BX and C lies on the chord XY. Show that CY = AO.

5.  Let X be the set of non-negative integers. Find all functions f: X → X such that x f(y) + y f(x) = (x + y) f(x² + y²) for all x, y.

Solutions

Problem 1

What is the largest possible number of elements in a subset of {1, 2, 3, ... , 9} such that the sum of every pair (of distinct elements) in the subset is different?

Solution

{1, 2, 3, 5, 8} has five elements and all pairs with a different sum. If there is a subset with 6 elements, then it has 15 pairs, each with sum at least 1 + 2 = 3 and at most 8 + 9 = 17. There are only 15 numbers at least 3 and at most 17, so each of them must be realised. But the only pair with sum 3 is 1,2 and the only pair with sum 17 is 8, 9 and then 1 + 9 = 2 + 8. So six elements is impossible.

Problem 2

We say that the positive integer m satisfies condition X if every positive integer less than m is a sum of distinct divisors of m. Show that if m and n satisfy condition X, then so does mn.

Solution

Suppose k < mn. Then k = am + b, where 0 ≤ a < n, 0 ≤ b < m. We may write a as a sum of distinct divisors of n. Hence am is a sum of distinct divisors of mn, each of them at least m. Also b is a sum of distinct divisors of m, each of them less than m. Hence k is a sum of distinct divisors of mn.

Problem 3

Show that x³/(yz) + y³/(zx) + z³/(xy) ≥ x + y + z for any positive reals x, y, z. When do we have equality?

Solution

(x⁴ + y⁴)/2 ≥ x²y² with equality iff x = y. Hence x⁴ + y⁴ + z⁴ ≥ x²y² + y²z² + z²x² with equality iff x = y = z.

(x²y² + y²z²)/2 ≥ xy²z. Hence x²y² + y²z² + z²x² ≥xyz(x + y + z). So x⁴ + y⁴ + z⁴ ≥ xyz(x + y + z) with equality iff x = y = z. Dividing by xyz gives the required result.

Problem 4

ABC is an equilateral triangle. C lies inside a circle center O through A and B. X and Y are points on the circle such that AB = BX and C lies on the chord XY. Show that CY equals AO.

Solution

Let O be the center of the circle. Chasing angles around ABXY we find that triangles AYC and AOB. Hence YC = OB.

[Let ∠OBA = x. Then ∠ABX = 2x, so ∠XBC = 2x - 60^o, so ∠BCX = ∠BXC = 120^o - x. Hence ∠ACY = 180^o - 60^o - (120^o - x) = x. ∠AYC = 180^o - ∠ABX = 180^o - 2x, so ∠YAC = x.]

Problem 5

Let X be the set of non-negative integers. Find all functions f: X → X such that x f(y) + y f(x) = (x + y) f(x² + y²) for all x, y.

Solution

Putting x = 0 we get y f(0) = y f(y²), so f(y²) = f(0) for all y. That strongly suggests f is constant. Obviously any constant function satisfies the condition.

Suppose f(x) < f(y) and neither x nor y is zero, then (x + y) f(x) < x f(y) + y f(x) < (x + y) f(y). Hence f(x) < f(x² + y²) < f(y). But that is impossible, because we could repeat the argument to get an infinite number of distinct values between f(x) and f(y). But we know that f(1) = f(0). Hence f(x) = f(1) for all x > 1. So f is constant.

[Read More...]

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.

[Read More...]

32nd Canadian Mathematical Olympiad Problems 2000

32nd Canadian Mathematical Olympiad Problems 2000

1.  Three runners start together and run around a track length 3L at different constant speeds, not necessarily in the same direction (so, for example, they may all run clockwise, or one may run clockwise). Show that there is a moment when any given runner is a distance L or more from both the other runners (where distance is measured around the track in the shorter direction).

2.  How many permutations of 1901, 1902, 1903, ... , 2000 are such that none of the sums of the first n permuted numbers is divisible by 3 (for n = 1, 2, 3, ... , 2000)?

3.  Show that in any sequence of 2000 integers each with absolute value not exceeding 1000 such that the sequence has sum 1, we can find a subsequence of one or more terms with zero sum.

4.  ABCD is a convex quadrilateral with AB = BC, ∠CBD = 2 ∠ADB, and ∠ABD = 2 ∠CDB. Show that AD = DC.

5.  A non-increasing sequence of 100 non-negative reals has the sum of the first two terms at most 100 and the sum of the remaining terms at most 100. What is the largest possible value for the sum of the squares of the terms? 

Problem 1

Three runners start together and run around a track length 3L at different constant speeds, not necessarily in the same direction (so, for example, they may all run clockwise, or one may run clockwise). Show that there is a moment when any given runner is a distance L or more from both the other runners (where distance is measured around the track in the shorter direction).

Solution

Let the runners be A, B, C. Using a rotating frame, if necessary, we may take A to be at rest. wlog B is faster than C. Take the first time when C reaches a point L from the start. If B is not more than twice as fast as C, then B will also be a distance at least L from the start (whichever way B runs). If B runs more than twice as fast as C, then whilst C runs the next distance L around the track, C is always at least L from A and B runs a distance of at least 2L. At some point during this period B must also be a distance at least L from A. 

Problem 2

How many permutations of 1901, 1902, 1903, ... , 2000 are such that none of the sums of the first n permuted numbers is divisible by 3 (for n = 1, 2, 3, ... , 2000)?

Solution

There are 34 numbers equal to 2 mod 3, and 33 each equal to 0 and 1 mod 3. The multiples of 3 do not affect the values mod 3, so consider the sequence of the other terms. Call terms equal to 1 mod 3, 1-terms and terms equal to 2 mod 3, 2-terms. If we start with a 1-term, then the next term must be a 1-term. The sum is then 2 mod 3, so the next term must be a 2-term, the sum is then 1 mod 3 and so the next term must be a 1-term, and so on. So after the first two terms, we must alternate between 1-terms and 2-terms. Similarly, if we start with a 2-term, the next term must be a 2-term, but then we must alternate. But there are more 2-terms than 1-terms, so we cannot start with a 1-term. Thus (ignoring the terms divisible by 3), the sequence must be 2-term, 2-term, 1-term, 2-term, 1-term, ... , 2-term, 1-term.

Thus we may start by placing the terms divisible by 3 in any positions except the first. That gives 99!/66! possibilities. The pattern of 2-terms and 1-terms is then determined and so in each case there are 34! 33! ways or arranging the 2-terms and 1-terms. Thus there are (99! 34! 33!)/66! possibilities in all. 

Problem 3

Show that in any sequence of 2000 integers each with absolute value not exceeding 1000 such that the sequence has sum 1, we can find a subsequence of one or more terms with zero sum.

Solution

Suppose the result is false. We can permute the sequence to a₁, a₂, ... , a₂₀₀₀ so that a_n has opposite sign to s_n-1 = a₁ + a₂ + ... + a_n-1 for n > 1. This is easily proved by induction. Note that no terms can be zero, or we would have a subsequence of one term with zero sum. Having chosen a₁, ... , a_n-1 with n < 2000, we the remaining terms have sum 1 - s_n-1. We cannot have s_n-1 = 0 or 1 otherwise we have a zero sum subsequence (with a₁, ... , a_n-1 or the remaining terms), hence the sum of the remaining terms has opposite sign to s_n-1. So we can find at least one term with the opposite sign to s_n-1.

Now consider the values assumed by s₁, s₂, ... , s_n. Each value must be different from zero (or we would have a zero sum subsequence) and only s₁ can have the value 1000 or -1000. Thus there are at most 1999 values available. So two terms s_m and s_n with m < n must have the same value. But then a_m+1 + ... + a_n = 0. 

Problem 4

ABCD is a convex quadrilateral with AB = BC, ∠CBD = 2 ∠ADB, and ∠ABD = 2 ∠CDB. Show that AD = DC.

Solution

Let the diagonals intersect at E and extend the ray DB to meet the circle center B radius BA at F. Then ∠BFC = ∠ADB and ∠BFA = ∠BDB. So AFCD is a parallelogram, so its diagonals bisect each other, so E is the midpoint of AC. But ABC is isosceles, so DF and AC are perpendicular. Hence AD = DC. 

Problem 5

A non-increasing sequence of 100 non-negative reals has the sum of the first two terms at most 100 and the sum of the remaining terms at most 100. What is the largest possible value for the sum of the squares of the terms?

Solution

Let the sequence by x₁, x₂, ... , x₁₀₀. Given any sequence satisfying the conditions with the sum of the first two terms less than 100, we can obtain another sequence which also satisfies the conditions and has larger sum of squares by increasing the first term. So we may assume that x₁ + x₂ = 100. So the sum of squares is at most (100 - x₂)² + x₂² + ... + x₁₀₀² = 10000 + 2x₂² - 200x₂ + x₃² + ... + x₁₀₀² <= 10000 + 2x₂² - x₂(x₁ + x₂ + ... + x₁₀₀) + x₃² + ... + x₁₀₀² = 10000 + x₂(x₂ - x₁) + x₃(x₃ - x₂) + ... + x₁₀₀(x₁₀₀ - x₂).

Hence the maximum value is 10000 and is achieved iff all of x₂(x₂ - x₁), x₃(x₃ - x₂), ... , x₁₀₀(x₁₀₀ - x₂) are zero.

x₂(x₂ - x₁) = 0 implies either x₂ = 0 or x₂ = x₁. The former gives the unique solution x₁ = 100, other terms zero. The latter implies x₁ = x₂ = 50 and every other term must be 0 or 50, which gives the unique solution 50, 50, 50, 50, 0, ... , 0.

[Read More...]

31st Canadian Mathematical Olympiad Problems 1999

31st Canadian Mathematical Olympiad Problems 1999

1.  Find all real solutions to the equation 4x² - 40[x] + 51 = 0.

2.  ABC is equilateral. A circle with center on the line through A parallel to BC touches the segment BC. Show that the length of arc of the circle inside ABC is independent of the position of the circle.

3.  Find all positive integers which equal the square of their number of positive divisors.

4.  X is a subset of eight elements of {1, 2, 3, ... , 17}. Show that there are three pairs of (distinct) elements with the same difference.

5.  x, y, z are non-negative reals with sum 1, show that x²y + y²z + z²x ≤ 4/27. When do we have equality?

Solutions

Problem 1

Find all real solutions to the equation 4x² - 40[x] + 51 = 0.

Solution

Answer: 2x = √29, √189, √229 or √269.

To orient ourselves notice that 4x² - 40x + 51 = (2x - 17)(2x - 3), so we expect roots to lie in the range 1 to 9.

Let f(x) = 4x² - 40[x] + 51. For x <= 1 f(x) > 51, so there are no solutions with x < 1.

f(1) = 15, f(2^-) = 16 - 40 + 51 = 27, so there are no solutions in the interval [1, 2).

f(2) = -13, f(3^-) = 7, so we expect a solution in [2, 3). For all x in this interval we have f(x) = 4x² - 29, so the unique solution is 2x = √29.

f(3) = -33, f(4^-) = -5, so there are no solutions in [3, 4).

f(4) = -45, f(5^-) = -9, so there are no solutions in [4, 5).

f(5) = -49, f(6^-) = -5, so there are no solutions in [5, 6).

f(6) = -45, f(7^-) = 7, so we expect a solution in [6, 7). For all x in this interval we have f(x) = 4x² - 189, so the unique solution is 2x = √189.

f(7) = -33, f(8^-) = 27. For all x in the interval [7, 8) we have f(x) = 4x² - 229, so the unique solution is 2x = √229.

f(8) = -13, f(9^-) = 55. For all x in the interval [8, 9) we have f(x) = 4x² - 269, so the unique solution is 2x = √269.

f(9) = 15. f(10^-) = 91, so there are no solutions in [9, 10). For x >= 10, we have 4x² - 40[x] + 51 ≥ 4x² - 40x + 51 = 4x(x - 10) + 51 > 0, so there are no solutions.

Problem 2

ABC is equilateral. A circle with center on the line through A parallel to BC touches the segment BC. Show that the length of arc of the circle inside ABC is independent of the position of the circle.

Solution

Let the circle meet the segment AC at X and the line AB at Y with Y outside the segment AB. Let O be the center of the circle. Then ∠OAY = ∠OAC = 60^o. But the line OA is a diameter of the circle, so XY must be perpendicular to AO and hence ∠AYX = 30^o. So the arc inside the circle subtends the constant angle 30^o at the circumference, so it must have constant length.

Problem 3

Find all positive integers which equal the square of their number of positive divisors.

Solution

Let N = p^aq^b ... . Then the square of the number of positive divisors of N is (a + 1)²(b + 1)² ... . Any square has all its prime factors to an even power, so a, b, ... must all be even. So writing a = 2m, b = 2n etc, we have p^mqⁿ ... = (2m+1)(2n+1) ... . Since the rhs is odd, all the primes p, q, ... must be odd.

A trivial induction shows that 2n + 1 < 3ⁿ for n > 1. Hence 2n + 1 < pⁿ for n > 1 for any odd prime p. For n = 1, 2n + 1 = 3 < p unless p = 3. So 2n+1 < pⁿ, where p is an odd prime and n is a positive integer, except in the case n = 1, p = 3.

Thus we can have at most one prime p in the factorisation of N and N = 1 or 3².

Problem 4

X is a subset of eight elements of {1, 2, 3, ... , 17}. Show that there are three pairs of (distinct) elements with the same difference.

Solution

Let the elements of X be a₁ < a₂ < ... < a₈. The 7 differences a₂ - a₁, a₃ - a₂, ... a₈ - a₇ have sum a₈ - a₁. The 6 differences a₃ - a₁, a₄ - a₂, ... , a₈ - a₆ have sum a₈ + a₇ - a₁ - a₂. So the 13 differences together have sum 2a₈ + a₇ - a₂ - 2a₁ ≤ 34 + 16 - 2 - 2 = 46. But if no difference occurs more than twice then the sum must be at least 2(1 + 2 + 3 + 4 + 5 + 6) + 7 = 49.

Problem 5

x, y, z are non-negative reals with sum 1, show that x²y + y²z + z²x ≤ 4/27. When do we have equality?

Solution

Assume x ≥ y, z. We have (x + z/2)²(y + z/2) - x²y - y²z - z²x = (x - y)yz + xz(x - z)/2 + yz²/4 + z³/8 > 0, unless z = 0. So if z > 0, we get a larger sum for x' = x+z/2, y' = y+z/2, z' = 0. So we can assume z = 0.

By AM/GM applied to x, x, 2y, we have 2x²y ≤ ( (2x + 2y)/3)³ = 8/27 and hence x²y ≤ 4/27 with equality iff x = 2/3, y = 1/3. Thus the original inequality holds with equality iff (x, y, z) = (2/3, 1/3, 0), (0, 2/3, 1/3) or (1/3, 0, 2/3).

[Read More...]

30th Canadian Mathematical Olympiad Problems 1998

30th Canadian Mathematical Olympiad Problems 1998

1.  How many real x satisfy x = [x/2] + [x/3] + [x/5]?

2.  Find all real x equal to √(x - 1/x) + √(1 - 1/x).

3.  Show that if n > 1 is an integer then (1 + 1/3 + 1/5 + ... + 1/(2n-1) )/(n+1) > (1/2 + 1/4 + ... + 1/2n)/n.

4.  The triangle ABC has ∠A = 40^o and ∠B = 60^o. X is a point inside the triangle such that ∠XBA = 20^o and ∠XCA = 10^o. Show that AX is perpendicular to BC.

5.  Show that non-negative integers a <= b satisfy (a² + b²) = n²(ab + 1), where n is a positive integer, iff they are consecutive terms in the sequence a_k defined by a₀ = 0, a₁ = n, a_k+1 = n²a_k - a_k-1.

Solutions

Problem 1

How many real x satisfy x = [x/2] + [x/3] + [x/5]?

Solution

Answer: 30.

Put x = 30q + r, where q is an integer and 0 ≤ r < 30. Then x - [x/2] - [x/3] - [x/5] = -q + r - [r/2] - [r/3] - [r/5]. So x = [x/2] + [x/3] + [x/5] iff q = r - [r/2] - [r/3] - [r/5].

q, [r/2], [r/3] and [r/5] are all integers, so r must be an integer. There are 30 possible integral values of r (namely 0, 1, 2, ... , 29), so there is one solution x for each.

Problem 2

Find all real x equal to √(x - 1/x) + √(1 - 1/x).

Solution

Squaring are rearranging: x³ - x² - x - 2 = 2√(x³ - x² - x + 1). Squaring again, x²(x⁴ - 2x³ - x² - 2x + 1) = 0. Referring to the original equation, x = 0 is not a solution, so we must have x⁴ - 2x³ - x² - 2x + 1 = 0. Factorising (x² - x - 1)² = 0, so x = (1 + √5)/2 or (1 - √5)/2. But referring to the original equation, we must have x ≥ 1, so the only candidate is x = (1 + √5)/2.

With this value 1/x = (√5 - 1)/2, so x - 1/x = 1 and 1 - 1/x = ( (√5 - 1)/2)² and hence √(x - 1/x) + √(1 - 1/x) = x, as required.

Problem 3

Show that if n > 1 is an integer then (1 + 1/3 + 1/5 + ... + 1/(2n-1) )/(n+1) > (1/2 + 1/4 + ... + 1/2n)/n.

Solution

We have 1/2 + 1/3 + 1/5 + ... + 1/(2n-1) > 1/2 + 1/4 + 1/6 + ... + 1/2n). Also 1/2 + 1/2 + ... + 1/2 ≥ 1/2 + 1/4 + ... + 1/(2n), so 1/2 ≥ (1/2 + 1/4 + ... + 1/(2n) )/n. Adding, 1 + 1/3 + 1/5 + ... + 1/(2n-1) > (1/2 + 1/4 + ... + 1/(2n) )(1 + 1/n).

Problem 4

The triangle ABC has ∠A = 40^o and ∠B = 60^o. X is a point inside the triangle such that ∠XBA = 20^o and ∠XCA = 10^o. Show that AX is perpendicular to BC.

Solution

We use Ceva's theorem. (sin BAX/sin CAX) (sin ACX/sin BCX) (sin CBX/sin ABX) = 1. So, putting ∠BAX = x, we have sin x sin 10^o sin 40^o = sin(40^o-x) sin 70^o sin 20^o. But sin 40^o = 2 sin 20^o cos 20^o = 2 sin 20^o sin 70^o, so 2 sin x sin 10^o = sin(40^o-x). Putting x = 30^o + y, we get 2 sin(30^o+y) sin 10^o = sin(10^o-y). Expanding: cos y sin 10^o + √3 sin y sin 10^o = sin 10^o cos y - cos 10^o sin y, so sin y(cos 10^o + √3 cos 10^o) = 0. Hence sin y = 0, so y = 0^o and x = 30^o. So AX is perpendicular to BC (the angle between AX and BC is 180^o - 30^o - 60^o = 90^o).

Problem 5

Show that non-negative integers a ≤ b satisfy (a² + b²) = n²(ab + 1), where n is a positive integer, iff they are consecutive terms in the sequence a_k defined by a₀ = 0, a₁ = n, a_k+1 = n²a_k - a_k-1.

Solution

If n = 1, then the sequence is 0, 1, 1, 0, -1, -1, 0, 1, 1, ... . Thus the only consecutive non-negative terms a, b with a ≤ b are 0, 1 and 1, 1 both of which satisfy the equation.

Conversely suppose that a ≤ b is a solution for n = 1. Then a² + b² = ab + 1. If 1 < a, then 1 < a², ab ≤ b², so 1 + ab < a² + b². Contradiction. So a = 0 or 1. If a = 0, then b² = 1, so b = 1. If a = 1, then 1 + b² = b + 1, so b = 0 or 1, but b ≥ a = 1, so b = 1. Thus the only solutions are a = 0, b = 1, or a = 1, b = 1.

So assume n > 1. It is a trivial induction to show that a_k < a_k+1. Now it is an easy induction on k to show that consecutive terms a_k-1, a_k satisfy the equation. It is true for k = 1: (0² + n²) = n²(0.n + 1). Suppose it is true for k. Then we have a_k+1 + a_k-1 = n²a_k. Hence a_k+1² - a_k-1² = n²a_k(a_k+1 - a_k-1). Adding to a_k² + a_k-1² =n²(a_ka_k-1 + 1), we get a_k+1² + a_k² =n²(a_k+1a_k + 1), which completes the induction.

Now suppose that a ≤ b is any solution in non-negative integers of a² + b² = n²(ab + 1). The idea is to show that n²a - b, a is a smaller solution.

If a = b, then 2a² = n²(a² + 1) ≥ 4(a² + 1) > 2a². Contradiction. So a < b. If a = 0, then b² = n², so b = n. This solution belongs to the sequence. So assume a > 0.

If b > n²a, then b >= n²a + 1, so b² ≥ n²ab + b > n²ab + n²a ≥ n²(ab + 1), so a² + b² > n²(ab + 1). Contradiction. So n²a - b ≥ 0. If n²a ≥ a + b, then n²ab ≥ ab + b² > a² + b². Contradiction. So n²a - b < a. Finally, (n²a - b)² + a² = n⁴a² - 2n²ab + a² + b² = n²( a(n²a - b) + 1) + (a² + b² - n²(ab + 1) ), so if a, b is a solution, then so is n²a - b, a.

Thus if we start with any solution 0 < a ≤ b, we can derive a solution a' < a, where the relationship between a', a and b is the same as that between a_k-1, a_k and a_k+1. This process must terminate, so eventually we get a solution 0, c. But we have shown that this must be 0, n. So we must have been moving down the sequence a_k. Hence a, b must be consecutive terms in that sequence.

[Read More...]

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) ).

[Read More...]

28th Canadian Mathematical Olympiad Problems 1996

28th Canadian Mathematical Olympiad Problems 1996

1.  The roots of x³ - x - 1 = 0 are r, s, t. Find (1 + r)/(1 - r) + (1 + s)/(1 - s) + (1 + t)/(1 - t).

2.  Find all real solutions to the equations x = 4z²/(1 + 4z²), y = 4x²/(1 + 4x²), z = 4y²/(1 + 4y²).

3.  Let N be the number of permutations of 1, 2, 3, ... , 1996 in which 1 is fixed and each number differs from its neighbours by at most 2. Is N divisible by 3?

4.  In the triangle ABC, AB = AC and the bisector of angle B meets AC at E. If BC = BE + EA find angle A.

5.  Let x₁, x₂, ... , x_m be positive rationals with sum 1. What is the maximum and minimum value of n - [n x₁] - [n x₂] - ... - [n x_m] for positive integers n? 

Solutions

Problem 1

The roots of x³ - x - 1 = 0 are r, s, t. Find (1 + r)/(1 - r) + (1 + s)/(1 - s) + (1 + t)/(1 - t).

Solution

Put y = (1 + x)/(1 - x). Then x = (y - 1)/(y + 1), so y satisfies (y - 1)³ - (y - 1)(y + 1)² - (y + 1)³ = 0 or y³ + 7y² - y + 1 = 0. So the sum of the roots is -7. 

Problem 2

Find all real solutions to the equations x = 4z²/(1 + 4z²), y = 4x²/(1 + 4x²), z = 4y²/(1 + 4y²).

Solution

It is immediate from the equations given that 0 <= x, y, z < 1. Rearranging, we have 4z² = x/(1 - x), 4x² = y/(1 - y), 4y² = z/(1 - z). Multiplying gives (xyz)²(1 - x)(1 - y)(1 - z) = xyz/64. If x = 0, then from the first equation in the question, z = 0 and hence also y = 0. That is one solution. Otherwise we have xyz non-zero and hence x(1 - x) y(1 - y) z(1 - z) = 1/64. But x(1 - x) = 1/4 - (x - 1/2)² <= 1/4 with equality iff x = 1/2. Similarly for y and z, so the only other solution is x = y = z = 1/2. 

Problem 3

Let N be the number of permutations of 1, 2, 3, ... , 1996 in which 1 is fixed and each number differs from its neighbours by at most 2. Is N divisible by 3?

Solution

Let the number of permutations of 1, 2, ... , n with 1 fixed and each number differing from its neighbours by at most 2 be p(n). The first number must be 1, so the second number must be 2 or 3. If the second number is 2, then the number of permutations of 2, 3, ... , n with 2 fixed and each number differing from its neighbours by at most 2 is p(n-1). If the second number is 3, then the third number is 2, 4 or 5. If it is 2, then the fourth number must be 4. In that case, the number of permutations of 4, 5, ... , n with 4 fixed etc is p(n-3). So suppose it is not 2.

If we get two adjacent numbers (m m+1 or m m-1) then either all following numbers are greater or all following numbers are less. In the sequence 1, 3, ... we have missed out a smaller number, namely 2, so after the first even number we must go back to it. Hence after the first even number we cannot have any larger numbers. In other words, the only possibility for 1, 3, (not 2), ... is all the odd numbers in increasing sequence followed by all the even numbers in decreasing sequence, eg 1, 3, 5, 7, 9, 8, 6, 4, 2.

Thus we have established that p(n) = p(n-1) + p(n-3) + 1. Checking the first few values, we find p(1) = 1, p(2) = 1, p(3) = 2, p(4) = 4, p(5) = 6, p(6) = 9. So mod 3, we have:

n    1   2   3   4   5   6   7   8     9  10  11  12  13  14  15  16    17

p(n) 1   1   2   1   0   0   2   0     1   1   2   1   0   0   2   0     1

So there is a cycle of length 8. 1996 = 4 mod 8, so p(1996) = p(4) = 1 mod 3. 

Problem 4

In the triangle ABC, AB = AC and the bisector of angle B meets AC at E. If BC = BE + EA find angle A.

Solution

Take X on BC with BX = BE. Then CX = AE and so CX/CE = AE/CE = AB/BC = AC/BC. The the triangles BAC and CXE have a common angle C and the ratio of the two sides containing the angle the same. Hence they are similar. So XC = XE. Hence ∠BXE = 2 ∠C. But ∠C = 90^o - A/2 and ∠BXE = 90^o - B/4 (since BEX is isosceles) = 90^o - (90^o - A/2)/4. Solving gives A = 100^o. 

Problem 5

Let x₁, x₂, ... , x_m be positive rationals with sum 1. What is the maximum and minimum value of n - [n x₁] - [n x₂] - ... - [n x_m] for positive integers n?

Solution

[n x_i] ≤ n x_i and n(x₁ + ... + x_m) = n, so clearly the value cannot be less than 0. But we can achieve 0 by taking n to be (for example) the product of the denominators of the x_i. So the minimum value is 0.

If we take n to be one less than the product of the denominators, then every term has its absolute value reduced by 1, so we get a total value of m-1. But each of (n x_i - [n x_i]) is strictly less than one, so n - [n x₁] - ... - [n x_m] is less than m. It is an integer, so it is at most m - 1. Hence m - 1 is the maximum value.

[Read More...]

27th Canadian Mathematical Olympiad Problems 1995

27th Canadian Mathematical Olympiad Problems 1995

1.  Find g(1/1996) + g(2/1996) + g(3/1996) + ... + g(1995/1996) where g(x) = 9^x/(3 + 9^x).

2.  Show that x^xy^yz^z >= (xyz)^(x+y+z)/3 for positive reals x, y, z.

3.  A convex n-gon is divided into m quadrilaterals. Show that at most m - n/2 + 1 of the quadrilaterals have an angle exceeding 180^o.

4.  Show that for any n > 0 and k ≥ 0 we can find infinitely many solutions in positive integers to x₁³ + x₂³ + ... + x_n³ = y^3k+2.

5.  0 < k < 1 is a real number. Define f: [0, 1] → [0, 1] by f(x) = 0 for x ≤ k, 1 - (√(kx) + √( (1-k)(1-x) ) )² for x > k. Show that the sequence 1, f(1), f( f(1) ), f( f( f(1) ) ), ... eventually becomes zero.

Solutions

Problem 1

Find g(1/1996) + g(2/1996) + g(3/1996) + ... + g(1995/1996) where g(x) = 9^x/(3 + 9^x).

Solution

g(k) + g(1-k) = 1, so the sum is 997 + g(1/2) = 997 1/2. 

Problem 2

Show that x^xy^yz^z ≥ (xyz)^(x+y+z)/3 for positive reals x, y, z.

Solution

Assume x ≥ y ≥ z. Then x/z, x/y, y/z are all at least one and (x-z)/3, (x-y)/3, (y-z)/3 are all positive. Hence (x/z)^(x-z)/3, (x/y)^(x-y)/3, (y/z)^(y-z)/3 are all at least one. Hence their product is at least 1, which is the required relation. 

Problem 3

A convex n-gon is divided into m quadrilaterals. Show that at most m - n/2 + 1 of the quadrilaterals have an angle exceeding 180 degrees.

Solution

Suppose there are k vertices inside the n-gon. Then we have a total of n + k vertices, m + 1 faces and (4m + n)/2 edges. So using V + F = E + 2, we have n + k + m + 1 = 2m + n/2 + 1. Hence k = m - n/2 + 1. A quadrilateral can have at most one angle > 180^o. The vertex with that angle must be inside the n-gon (which is convex), so there are at most k quadrilaterals with an angle > 180^o. 

Problem 4

Show that for any n > 0 and k ≥ 0 we can find infinitely many solutions in positive integers to x₁³ + x₂³ + ... + x_n³ = y^3k+2.

Solution

It is sufficient to consider k = 0, for if N² is a sum of n positive cubes, then multiplying through by N^3k gives N^3k+2 as a sum of n positive cubes.

Moreover, it is sufficient to find a single example of N² as a sum of n positive cubes, for then multiplying through by any m⁶ gives a larger example.

But we have the familiar formula 1³ + 2³ + ... + n³ = ( n(n+1)/2 )². 

Problem 5

0 < k < 1 is a real number. Define f: [0, 1] → [0, 1] by f(x) = 0 for x ≤ k, 1 - (√(kx) + √( (1-k)(1-x) ) )² for x > k. Show that the sequence 1, f(1), f( f(1) ), f( f( f(1) ) ), ... eventually becomes zero.

Solution

We have f(1) = 1 - k. Also for x > k, f(x) = k + x - 2kx - 2 √(kx(1-k)(1-x) ). We have x > k, so (1-k) > (1-x) and kx(1-k)(1-x) > k²(1-x)² . Hence f(x) < k + x - 2kx - 2k(1-x) = x - k. So if x > k, then applying f reduces x by at least k. So applying it n times either reduces x below k or reduces it by at least nk. But k > 0, so applying f sufficiently many times must reduce x below k and thereafter it gives 0.

[Read More...]

26th Canadian Mathematical Olympiad Problems 1994

26th Canadian Mathematical Olympiad Problems 1994

1.  Find -3/1! + 7/2! - 13/3! + 21/4! - 31/5! + ... + (1994² + 1994 + 1)/1994!

2.  Show that every power of (√2 - 1) can be written in the form √(k+1) - √k.

3.  25 people sit in circle. They vote for or against an issue every hour. Each person changes his vote iff his vote was different from both his neighbours on the previous vote. Show that after a while no one's vote changes.

4.  AB is the diameter of a circle. C is a point not on the line AB. The line AC cuts the circle again at X and the line BC cuts the circle again at Y. Find cos ACB in terms of CX/CA and CY/CB.

5.  ABC is an acute-angled triangle. K is a point inside the triangle on the altitude AD. The line BK meets AC at Y, and the line CK meets AB at Z. Show that ∠ADY = ∠ADZ.

Solutions

Problem 1

Find -3/1! + 7/2! - 13/3! + 21/4! - 31/5! + ... + (1994² + 1994 + 1)/1994!

Solution

∑ (-1)ⁿ (n/n! + 1/n!) = -1 + 1/1994! (the series telescopes). Similarly, ∑ (-1)ⁿ n²/n! = ∑ (-1)ⁿ n/(n-1)! = ∑ (-1)ⁿ (1/(n-2)! + 1/(n-1)! ) = 1/1993! . So expression given is -1 + 1/1994! + 1/1993! = -1 + 1995/1994! .

Problem 2

Show that every power of (√2 - 1) can be written in the form √(k+1) - √k.

Solution

Put a = (√2 - 1)ⁿ, b = (√2 + 1)ⁿ. Put c = (b + a)/2, d = (b - a)/2, so that a = c - d. Expanding by the binomial theorem, we see that for n even, c and d/√2 are both integers, and for n odd, c/√2 and d are integers. So for any n, c² and d² are integers. But c² - d² = ab = 1. Thus putting k = d², we have a = √(k+1) - √k.

Comment. There are many different approaches to this problem, all of which work!

Problem 3

25 people sit in circle. They vote for or against an issue every hour. Each person changes his vote iff his vote was different from both his neighbours on the previous vote. Show that after a while no one's vote changes.

Solution

Let S_n be the set of people who do not change their votes at round n (for n > 1). Obviously S_n is a subset of S_n+1. Suppose S_n is non-empty but does not include everyone. Then we can find two adjacent people x in S_n and y not in S_n. Since y voted differently in round n, y must have voted the opposite way to x in round n-1. But x votes the same way in round n, so y must vote the same way as x in round n. Hence y belongs to S_n+1. So if S₂ is non-empty then S_n keeps on growing until it includes everyone.

That is true for any n. But if n is even, then it is possible to have S₂ empty. As you move around the circle people vote alternately for and against. If n is odd, that is impossible.

Problem 4

AB is the diameter of a circle. C is a point not on the line AB. The line AC cuts the circle again at X and the line BC cuts the circle again at Y. Find cos ACB in terms of CX/CA and CY/CB.

Solution

Answer: cos²ACB = (CX/CA).(CY/CB). It is the positive root for C outside the circle and the negative root for C inside the circle.

For C outside the circle, we have cos ACB = CX/CB = CY/CA (one should check that this is true in all configurations). Hence result.

For C on the circle it is still true because cos ACB = 0 and CX = CY = 0. For C inside the circle, cos ACB = - cos ACY = - CY/CA and also = - cos BCX = - CX/CB.

Problem 5

ABC is an acute-angled triangle. K is a point inside the triangle on the altitude AD. The line BK meets AC at Y, and the line CK meets AB at Z. Show that ∠ADY = ∠ADZ.

Solution

Let the rays DZ, DY meet the line through A parallel to BC at U, V respectively. Then UZA is similar to DZB, so UA/ZA = DB/ZB. Similarly VA/YA = DC/YC. Hence UA/VA = ZA (DB/ZB) (YC/DC) 1/YA = (DB/DC) (YC/YA) (ZA/ZB). But that is 1 by Ceva's theorem. Hence UA = VA, so ∠ADZ = ∠ADY.

[Read More...]

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.

[Read More...]

24th Canadian Mathematical Olympiad Problems 1992

24th Canadian Mathematical Olympiad Problems 1992

1.  Show that n! is divisible by (1 + 2 + ... + n) iff n+1 is not an odd prime.

2.  Show that x(x - z)² + y(y - z)² ≥ (x - z)(y - z)(x + y - z) for all non-negative reals x, y, z. When does equality hold?

3.  ABCD is a square. X is a point on the side AB, and Y is a point on the side CD. AY meets DX at R, and BY meets CX at S. How should X and Y be chosen to maximise the area of the quadrilateral XRYS?

4.  Find all real solutions to x²(x + 1)² + x² = 3(x + 1)².

5.  There are 2n+1 cards. There are two cards with each integer from 1 to n and a joker. The cards are arranged in a line with the joker in the center position (with n cards each side of it). For which n < 11 can we arrange the cards so that the two cards with the number k have just k-1 cards between them (for k = 1, 2, ... , n)?

Solutions

Problem 1

Show that n! is divisible by (1 + 2 + ... + n) iff n+1 is not an odd prime.

Solution

For n = 1, we have to show that 1 divides 1, which is obvious. So assume n > 1. We have 1 + 2 + ... + n = n(n+1)/2. So we have to show that n+1 divides (n-1)! for n+1 not a prime. But that is obvious except possibly in the case n+1 = p². However, in that case p and 2p < n, so p² still divides (n-1)! . [The converse, that if n+1 is an odd prime then it does not divide n!, is obvious.]

Problem 2

Show that x(x - z)² + y(y - z)² >= (x - z)(y - z)(x + y - z) for all non-negative reals x, y, z. When does equality hold?

Solution

Answer: equality iff x = y = z or x = y and z = 0.

Put u = x - z, v = y - z. Then x(x - z)² + y(y - z)² - (x - z)(y - z)(x + y - z) = (u + z)u² + (v + z)v² - uv(u + v + z) = (u + v)(u - v)² + z(u² - uv + v²). If u and v are both non-negative, then this is obviously non-negative (since u² - uv + v² = (u - v)² + uv) and zero only if u = v = 0 or u = v and z = 0 (in other words, x = y = z or x = y and z = 0).

If just one of u, v is negative, then the rhs of the original expression is negative or zero and the rhs is positive, so strict inequality holds.

If both u and v are negative, then we may assume x + y > z (otherwise the lhs of the original expression is positive and the rhs negative or zero). But in that case z > -(u + v) and u² - uv + v² > (u - v)², so z(u² - uv + v²) > -(u + v)(u - v)².

Problem 3

ABCD is a square. X is a point on the side AB, and Y is a point on the side CD. AY meets DX at R, and BY meets CX at S. How should X and Y be chosen to maximise the area of the quadrilateral XRYS?

Solution

Answer: the maximum area of (area ABCD)/4 is achieved whenever XY is parallel to AD.

Area XRYS = area XRS + area YRS. Area XRS = (XR/XD) area XSD = (XR/XD) (XS/XC) area XDC = (XR/XD) (XS/XC) (area ABCD)/2. Similarly, area YRS = (YS/BY) (RY/AY) (area ABCD)/2. But XR/XD = 1 - YR/AY, XS/XC = 1 - YS/BY. So if we put XR/XD = (1/2 + x), XS/XC = (1/2 + y), then area XRYS = (1/4 + xy) area ABCD.

But triangles ARX and YRD are similar, so XR > DR iff AX > YD. Similarly, XS > SC iff BX > CY. Hence XR/XD > 1/2 iff XS/XC < 1/2 and XR/XD = 1/2 iff XS/XC = 1/2. Thus either x = y = 0 or xy is negative. If x = y = 0, then XY is parallel to AD.

Problem 4

Find all real solutions to x²(x + 1)² + x² = 3(x + 1)².

Solution

Expanding, x⁴ + 2x³ - x² - 6x - 3 = 0. Factorising, (x² - x - 1)(x² + 3x + 3) = 0. The first quadratic has real roots x = 1/2 ± (√5)/2. The second quadratic is (x + 3/2)² + 3/4, so has no real roots.

Problem 5

There are 2n+1 cards. There are two cards with each integer from 1 to n and a joker. The cards are arranged in a line with the joker in the center position (with n cards each side of it). For which n < 11 can we arrange the cards so that the two cards with the number k have just k-1 cards between them (for k = 1, 2, ... , n)?

Solution

Consider the number of pairs (i, j) where i lies between the two j's or j lies between the two i's (if both i's or both j's do then we count both). The number must be 0 or 2, because we have either i ... i ... j ... j or i ... j ... i ... j or j ... i ... i ... j or i ... j ... j ... i or j ... i ... j ... i or j ... j ... i ... i. So the sum over all such pairs is even. But the sum is also 1 + 2 + ... + (n-1) = (n-1)n/2 less the number of pairs which straddle the joker. If n is even, then an even number of pairs must straddle the joker and if n is odd an odd number of pairs. So if n = 4m+1, then the sum is even less odd = odd, and so 4m+1 is impossible. Similarly, if n = 4m+2, then the sum is odd less even = odd, so 4m+2 is impossible. Thus we must have n = 0 or 3 mod 4. In particular, n = 1, 2, 5, 6, 9, 10 are impossible. We show below that n = 3, 4, 7, 8 are possible.

1 1 3 J 2 3 2

1 1 3 4 J 3 2 4 2

1 1 2 5 2 6 7 J 5 3 4 6 3 7 4

1 1 2 6 2 5 7 8 J 6 5 3 4 7 3 8 4

Comment. See also Chinese 86/B2. This is a variant on Langford's problem (which is the same except that there is no joker and we require k numbers between the two k's (not k-1).

[Read More...]