Communications of the ACM
Last byte
Puzzled: Solutions and Sources
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 original table.
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 (20032004) 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?
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1610252.1610278
©2009 ACM 0001-0782/09/1200 $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