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 a1, a2, ... , a2000 so that an has opposite sign to sn-1 = a1 + a2 + ... + an-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 a1, ... , an-1 with n < 2000, we the remaining terms have sum 1 - sn-1. We cannot have sn-1 = 0 or 1 otherwise we have a zero sum subsequence (with a1, ... , an-1 or the remaining terms), hence the sum of the remaining terms has opposite sign to sn-1. So we can find at least one term with the opposite sign to sn-1.
Now consider the values assumed by s1, s2, ... , sn. Each value must be different from zero (or we would have a zero sum subsequence) and only s1 can have the value 1000 or -1000. Thus there are at most 1999 values available. So two terms sm and sn with m < n must have the same value. But then am+1 + ... + an = 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 x1, x2, ... , x100. 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 x1 + x2 = 100. So the sum of squares is at most (100 - x2)2 + x22 + ... + x1002 = 10000 + 2x22 - 200x2 + x32 + ... + x1002 <= 10000 + 2x22 - x2(x1 + x2 + ... + x100) + x32 + ... + x1002 = 10000 + x2(x2 - x1) + x3(x3 - x2) + ... + x100(x100 - x2).
Hence the maximum value is 10000 and is achieved iff all of x2(x2 - x1), x3(x3 - x2), ... , x100(x100 - x2) are zero.
x2(x2 - x1) = 0 implies either x2 = 0 or x2 = x1. The former gives the unique solution x1 = 100, other terms zero. The latter implies x1 = x2 = 50 and every other term must be 0 or 50, which gives the unique solution 50, 50, 50, 50, 0, ... , 0.
Labels:
CMO
Previous Article
