13th Canadian Mathematical Olympiad Problems 1981

13th Canadian Mathematical Olympiad Problems 1981

1.  Show that there are no real solutions to [x] + [2x] + [4x] + [8x] + [16x] + [32x] = 12345.

2.  The circle C has radius 1 and touches the line L at P. The point X lies on C and Y is the foot of the perpendicular from X to L. Find the maximum possible value of area PXY (as X varies).

3.  Given a finite set of lines in the plane, show that an arbitrarily large circle can be drawn which does not meet any of them. Show that there is a countable set of lines in the plane such that any circle with positive radius meets at least one of them.

4.  p(x) and q(x) are real polynomials such that p(q(x) ) = q(p(x) ) and p(x) = q(x) has no real solutions. Show that p(p(x) ) = q(q(x) ) has no real solutions.

5.  11 groups perform at a festival. Each day any groups not performing watch the others (but groups performing that day do not watch the others). What is the smallest number of days for which the festival can last if every group watches every other group at least once during the festival? 

Solutions

Problem 1

Show that there are no real solutions to [x] + [2x] + [4x] + [8x] + [16x] + [32x] = 12345.

Solution

Let f(x) = [x] + [2x] + [4x] + [8x] + [16x] + [32x]. Obviously f is an increasing function (if x < y, then f(x) ≤ f(y).). f(196) = 12348. But if x is just under 196, then [x], [2x], [4x], [8x], [16x] and [32x] are all smaller by at least 1, so f(x) < 12342. Hence f never takes the value 12345. 

Problem 2

The circle C has radius 1 and touches the line L at P. The point X lies on C and Y is the foot of the perpendicular from X to L. Find the maximum possible value of area PXY (as X varies).

Solution

Answer: (3√3)/8.

Let O be the center of C and QP a diameter. Let ∠QOX = x. Then PY = sin x and XY = 1 + cos x, so the area is sin x(1 + cos x)/2. We claim that this has minimum value (3√3)/8. Put y = sin x, so √(1 - y²) = cos x. We have (y - 3√3/4y)² ≥ 0, so y² - (3√3)/2y + 27/16y² ≥ 0, or 27/16y² - (3√3)/2y + 1 ≥ 1 - y² (*). Now y ≤ 1, so (3√3)/4y > 1. Thus taking the positive square roots of (*) we get: (3√3)/4y - 1 ≥ √(1 - y²) or y(1 + √(1 - y²)) ≤ (3√3)/4, as claimed. 

Problem 3

Given a finite set of lines in the plane, show that an arbitrarily large circle can be drawn which does not meet any of them. Show that there is a countable set of lines in the plane such that any circle with positive radius meets at least one of them.

Solution

If all the lines are parallel, then there is an empty half-plane beyond the last line, in which we can put arbitraril large circles. If not, take the convex hull of all the points of intersection. Rays emerge from this hull and do not intersect outside it. Take two adjacent rays which are not parallel, then they diverge, so arbitrarily large circles can be accomodated between them.

Take lines parallel to the coordinate axes through every rational point on the other axis. 

Problem 4

p(x) and q(x) are real polynomials such that p(q(x) ) = q(p(x) ) and p(x) = q(x) has no real solutions. Show that p(p(x) ) = q(q(x) ) has no real solutions.

Solution

Suppose p(p(a)) = q(q(a)) for some real a. Put b = p(a), c = q(a). So p(b) = q(c). Note that since p(x) and q(x) are real polynomials, b and c are real. We cannot have b = c since p(x) = q(x) has no real solutions. Now p(c) =p(q(a)) = q(p(a)) = q(b). Now put r(x) = p(x) - q(x), then r(b) = p(b) - q(b). We cannot have r(b) = 0, since p(x) = q(x) has no real solutions. But r(b) = p(b) - q(b) = q(c) - p(c) = - r(c), so r(x) changes sign between x = b and x = c, so it must have a root between b and c. Contradiction. Hence p(p(x)) = q(q(x)) cannot have a real solution. 

Problem 5

11 groups perform at a festival. Each day any groups not performing watch the others (but groups performing that day do not watch the others). What is the smallest number of days for which the festival can last if every group watches every other group at least once during the festival?

Solution

Answer: 6 days.

It is not obvious how to approach this. Consider the case of n groups. It is easy to make do with n days. For example, on day i, group i performs and the others watch. Or vice versa. For n = 3, 3 days are necessary, 1 watching 2, 2 watching 3 and 3 watching 1 must occur on separate days. It is not quite as obvious that 4 days are needed for n = 4. Suppose three days suffice. Then on some day two groups perform. Wlog 1 and 2 perform on day 1. Then we need two more days for 1 to watch 2 and 2 to watch 1. So assume 1 watches 2 on day 2 and 2 watches 1 on day 3. The only day 1 is in the audience is day 2, so 3 and 4 must perform on day 2. Similarly, 2 is only in the audience on day 3, so 3 and 4 must perform on day 3. But now 3 and 4 must be in the audience on day 1 in order to watch 1 and 2. That means they cannot watch each other. So we need 4 days.

However, 4 days suffice for n = 6. For example:

1 2 3 watch 4 5 6

1 4 5 watch 2 3 6

2 4 6 watch 1 3 5

3 5 6 watch 1 2 4

Note that if m days suffice for n, then they also suffice for n-1 - just delete one group from the schedule. So 4 days also suffice for 5. They must be necessary, because otherwise we could do 4 groups in 3 days.

We can now do 12 groups in 6 days (and hence also 11 groups in 6 days):

1 2 3 A B C watch 4 5 6 D E F

1 4 5 A D E watch 2 3 6 B C F

2 4 6 B D F watch 1 3 5 A C E

3 5 6 C E F watch 1 2 4 A B D

1 2 3 4 5 6 watch A B C D E F

A B C D E F watch 1 2 3 4 5 6

Note that this is general. If m days suffice for n groups, then m+2 suffice for 2n groups. With a slight variant we can do 10 groups in 5 days:

1 2 3 A B C watch 4 5 6 D

1 4 5 A B D watch 2 3 6 C

2 4 6 A C D watch 1 3 5 B

3 5 6 B C D watch 1 2 4 A

1 2 3 4 5 6 watch A B C D

So to finish off we have to show that 5 days are not sufficient for 11 groups. If we also show that 4 are not sufficient for 7 groups, then we have dealt with all cases up to n = 12.

Consider n = 7. Suppose we only need 4 days. If a group only performs once, then the other 6 groups must watch that day. So none of them watch each other. So they need at least 4 days to watch each other and only 3 are available. So each group must perform at least twice. But that means on some day at least 4 groups perform (4 days x 3 groups < 7 groups x 2 performances). On that day none of the 4 can watch each other. But they need 4 days to watch each other. So 7 groups need at least 5 days.

Consider n = 11. Suppose we only need 5 days. Each day at least 6 groups are watching or at least 6 groups are performing. So there must be three days with at least 6 groups watching or three days with at least 6 groups performing. But that means that there are 4 groups which all perform on 2 days or which all watch on 2 days. In either case, they need a further 4 days to watch each other. Contradiction. [The claim that if 6 groups watch on three days, then we can find a particular set of 4 which watch on two of the three days is justified as follows. If only 3 watch on more than one day, then that leaves 8 who watch on just one day. So there is a day when at most 2 of the 8 watch. But then on that day at most 2 + 3 can watch, whereas 6 are supposed to.]

Summary:

n 3     4     5     6     7     8     9    10    11    12

days 3     4     4     4     5     5     5     5     6     6