Computing Applications Last byte

Puzzled: Figures on a 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. Article
  2. Author
  3. Footnotes
  4. Figures
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, Erd cacm5308_a.gif s, 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

Back to Top

Back to Top


F1 Figure 1.

F2 Figure 2.

Back to top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More