Communications of the ACM
Last byte
Puzzled: Covering the Plane
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...
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?
Footnotes
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1592761.1592786
©2009 ACM 0001-0782/09/1100 $10.00
Permission to make digital or hard copies of all or part 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 the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
No entries found