Solutions and Sources
Last month (November 2009, p. 112) we posted a trio of brain teasers,
including one as yet unsolved, concerning the covering of a plane.
1.identical Coins on Rectangular table.
Solution. Let us observe that if we double the radius (say, from one to two
inches) of each of the original coins,
the result would be to cover the whole
table. Why? Well, if a point P isn’t covered, it must be two inches or more
from any coin center; thus a one-inch
coin placed with its center at P would
fit in the original configuration.
If we could replace each big coin
with four small coins covering the
same area, we’d be done… but we can’t
cover a big coin with four small coins.
Instead, let us note that rectangles
have the property that they can be partitioned into four copies of themselves.
So, we shrink the whole picture (of big
coins covering the table) by a factor of
two in each dimension and use four
copies of the new picture to cover the
Surprisingly (perhaps), this lovely
but seemingly crude argument gives
the best possible factor: Replace the
factor 4 with anything smaller, say 3. 99,
and the statement of the puzzle (with
100 and 400 replaced by n and 3.99n) is
no longer true.
The puzzle came to me by way of
computer scientist Guy Kindler of the
School of Computer Science and Engineering in the Hebrew University of
Jerusalem during a marvelous visiting
year (2003–2004) by each of us at the
Institute for Advanced Study in Princeton, NJ.
2.two Sets of Parallel Lines on infinite Plane.
Solution. The puzzle asked whether
we could cover each point of the plane
exactly twice using a set of lines that
contains lines in more than two different directions.
The solution will disappoint some
of us. The answer is yes, assuming the
Axiom of Choice, which allows us to
make choices at every step of an infinite process. But the proof presented
here requires transfinite induction(!),
leaving us without any geometry we
can wrap our mind around. The problem (and its solution) were provided to
me by mathematical physicist Senya
Shlosman of the Centre de Physique
Theorique, Marseille, France, who is
unaware of its origin.
Nonetheless, the solution appeals
to me as an example of an easy application of a powerful tool. The idea is that
we start off with three lines that cross
one another (so we already have three
directions). Roughly speaking, at each
moment in our algorithm we have constructed a finite or countable number
of lines, with no point covered twice;
we then pick a point on the plane that
is not doubly covered and add a line
through that point. How do we know
we can do this without triple-covering
some other point? Because the number
of pairs of lines so far constructed is
countable, only countably many points
are double-covered, and we have an uncountable number of angles at which
the new line can be placed.
Does this seem like cheating? It
should. First, those of us who have
used transfinite induction know that
details have been omitted (but easily
supplied). More significant, there is no
way we can do this construction in a
useful manner. Does this mean there
isn’t some clever, effective, or at least
imaginable way to double-cover the
plane with lines, other than by two parallel classes? I haven’t found one. Neither has Shlosman. Perhaps you can.
3.Colored Discs on infinite Plane.
Conjecture. This open puzzle supposed that we were given a collection
of open-unit discs that is a thousandfold cover of the plane; that is, every
point of the plane is covered by at
least 1,000 discs. Our job was to prove
(or disprove) that we can color each
disc red or blue in such a way that the
red discs cover the plane and the blue
discs also cover the plane.
No solutions have been offered so
far. Maybe this is just fundamentally
very difficult to prove. Maybe it isn’t
even true. But it seems reasonable,
don’t you think?
All readers are encouraged to submit prospective
puzzles for future columns to firstname.lastname@example.org.
Peter Winkler ( email@example.com) is Professor of
Mathematics and of Computer Science and Albert Bradley
Third Century Professor in the Sciences at Dartmouth
College, Hanover, NH.