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
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
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 ( firstname.lastname@example.org) 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 email@example.com.