Sign In

Communications of the ACM

Last byte

Puzzled: Figures on a Plane


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Peter Winkler scrambled

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, Erdcacm5308_a.gifs, Fejes Tóth... or anyone waiting impatiently for, say, food to be served in a restaurant.

  1. 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.
  2. 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.
  3. 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 puzzled@cacm.acm.org.

Back to Top

Author

Peter Winkler (puzzled@cacm.acm.org) is Professor of Mathematics and of Computer Science and Albert Bradley Third Century Professor in the Sciences at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

DOI: http://doi.acm.org/10.1145/1787234.1787260

Back to Top

Figures

F1Figure 1.

F2Figure 2.

Back to top


©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