last byte

DOI: 10.1145/1592761.1592786
Peter Winkler
Puzzled
covering the Plane
Welcome to three new puzzles. Solutions to the first two will be published
next month; the third is (as yet) unsolved. In each, the issue is how your intuition
matches up with the mathematics.

1.One hundred identical coins lie flat on a rectangular table in such a way that no more coins can be added without the coins overlapping. (A coin is allowed to extend over the edge as long as its center is on the table.) Now the coins are cleared from the table, and you must prove you can cover the table with 400 of the same coins. (Again overhang is allowed, but this time the coins must overlap.)

The original layout of coins is called a maximal packing (of a rectangle by discs). What is sought is a covering, with the claim that it requires no more than four times as many discs as a maximal packing. One approach might be to try using 100 larger discs, then replace each of them with four of the original size. However, the second part doesn’t seem to work. What would you suggest?

2.Using two full sets of parallel lines, you can cover an infinite plane in such a way that every point belongs to exactly two lines (an arrangement called an exact double cover of the plane by lines). For example, you can use all the vertical lines and all the horizontal lines; every point on the plane belongs to one line from each category.

Is there another way to do it? Is there an exact double cover using lines that extend in more than two directions? For example, you could try taking all lines tangential to some fixed circle. This would work outside the circle but would hit each point on the circle only once and miss the inside entirely. Hmmm…

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

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.

3.Suppose you have a collection of open-unit discs covering a plane everywhere at least a thousand discs deep; that is, every point on the infinite plane is covered by at least a thousand discs. Now prove you can color each one red or blue in such a way that by themselves the red discs would cover the plane, and the blue discs would cover the plane. For each covering, each point of the plane must be in one or more discs of that color—surely not too much to ask.

Maybe not, but no one has proved it can be done, even for a billion-fold cover. János Pach of New York University is the originator of (and expert on) this wonderful open problem. In his paper “Covering the Plane with Convex Polygons” (Discrete and Computational Geometry 1, 1 (1986), 73–81), he proved that, for any symmetric polygon P, there is a number k such that any k-fold covering of the plane (by translates of P) can be partitioned into two separate covers. However, no such k is known when the polygon is a disc. Personally, I think k = 4 ought to be enough. What do you think?