last byte

DOI: 10.1145/2043174.2043200
Peter Winkler

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

Puzzled
Solutions and Sources
Last month (Nov. 2011, p. 120) we posted a trio of brainteasers, including
one as yet famously unsolved, concerning distances between points on
the plane. Here, we offer solutions to two of them. How did you do?

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 counter-
example, 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 can-
not be more than 60 degrees or else
the third side AC of the triangle would
be too long.

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!

 

Peter Winkler ( [e-mail]) is professor of mathematics and of Computer science, and albert bradley third Century professor in the sciences, at Dartmouth College, hanover, Nh.

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

All readers are encouraged to submit prospective puzzles for future columns to [e-mail].