Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, December 2011, Vol. 54 No. 12, Page 142
10.1145/2043174.2043200
Comments

1. Cities of gold.

Solution. You were asked to determine whether it is possible to place seven points (cities of gold) on the plane in such a way that among any three, at least two are a specified distance—10 leagues—apart. It turns out there is.

We can assume that the specified distance is 1. Two unit-side equilateral triangles sharing a side make what we call a "lozenge" with two sharp endpoints. Take two lozenges with a common sharp endpoint P, and swing them with P fixed in such a way that their other endpoints are unit distance apart (see the figure here). Together, the two lozenges have seven vertices. To see that they satisfy the condition, suppose there were three points among the seven that do not include a pair at distance 1. This threesome cannot contain the "fulcrum" point P, because all but two of the remaining six points are at unit distance from the fulcrum, and these two—the other sharp lozenge endpoints—are unit distance from each other. So forget the fulcrum, but the other six points lie on two equilateral triangles, and any three must include at least two vertices of one of the triangles.

This cute problem was passed to me (without the spurious history) by mathematical wizard Frank Morgan of Williams College.

2. Frisbee players.

Solution. If the Frisbee players are arranged in a regular nonagon with longest diagonals of length 100 yards, then nine pairs of players will be at this distance, with none farther.

In fact, for any n, you cannot get more than n "maxpairs," or pairs of points at maximum distance, among n points in the plane. To prove this, assume it is false, and let the points A,B,C...constitute a counterexample of the smallest possible size n.

Note first that any two maxpairs AB, CD must "cross"; that is, the line segment between A and B crosses the segment between C and D; otherwise one of the diagonals of the quadrilateral ABDC would exceed the supposed maximum length.

Now if, in our purported counterexample, no point was involved in more than two maxpairs, then there would be only n maxpairs in total. So there must be some point P that is in three maxpairs, say, PA, PB, and PC, in that order clockwise around P. Note that the angle between PA and PC cannot be more than 60 degrees or else the third side AC of the triangle would be too long.

Observe now that the point B cannot be involved in any other maxpairs, because such a pair would cross both PA and PC, an impossibility. Dropping B out of our configuration yields a smaller configuration with one fewer point and one fewer maxpair, reaching a contradiction.

This puzzle appeared in 1957 on the William Lowell Putnam Exam, an annual contest for college students (http://math.scu.edu/putnam/), which is a great source for challenging mathematical puzzles.

3. Three colors, seven points.

Solution. To see how the layout of the seven points in the first puzzle gives us information about painting the plane, consider the colors these seven points would have to be if you could paint with only three colors. By the pigeonhole principle (used several times already in this column) at least three of the seven points must then get the same color, but we know these three contain two points at unit distance, and points at unit distance are not allowed to have the same color. Voila!

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.

---

No entries found