Communications of the ACM
Last byte
Puzzled: Figures on a Plane
We examine simple but intriguing questions about figures on the plane. They are not, perhaps, the kinds of questions one would find in Euclid's Elements but more what could be expected from Minkowski, Erd
s, Fejes Tóth... or anyone waiting impatiently for, say, food to be served in a restaurant.
- On the tablecloth before us in one such restaurant is a gravy stain of an area less than one square inch. Meanwhile, in our briefcase is a large transparent sheet of plastic on which is printed a square grid of side one inch. Prove the sheet can be placed over the stain in such a way that no intersection point of the grid falls on the stain. Figure 1 shows a successful placement for a particular stain.
- On the table before us are 10 dots, and in our pocket are 10 $1 coins. Prove the coins can be placed on the table (no two overlapping) in such a way that all dots are covered. Figure 2 shows a valid placement of the coins for this particular set of dots; they are transparent so we can see them. The three coins at the bottom are not needed.
- What is the largest number n such that any n points on the plane can be covered by disjoint unit disks (like the coins in the second puzzle)? That is, what is the largest number we can replace the 10s by in the second puzzle so it remains true? We know from the solution to the second puzzle that the maximum n is at least 10. Your author can construct a pattern of 60 points (in a triangular lattice) that cannot be covered by disjoint unit disks, so n is less than 60. What is the true maximum value of n? I guess around 25, but it might be quite difficult to pin it down, even with a computer's help.
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2010 ACM 0001-0782/10/0800 $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 © 2010 ACM, Inc.
No entries found