acm-header
Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources


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 distance10 leaguesapart. 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 twothe other sharp lozenge endpointsare 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

Author

Peter Winkler (puzzled@cacm.acm.org) is Professor of Mathematics and of Computer Science, and Albert Bradley Third Century Professor in the sciences, at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

Back to Top

Figures

UF1Figure. Locations of the seven cities of gold, with each line representing a distance of 10 leagues; the top point is the fulcrum P.

Back to top


©2011 ACM  0001-0782/11/1200  $10.00

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

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


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents: