last byte

DOI: 10.1145/1787234.1787260
Peter Winkler
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.

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.

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 [e-mail]. Peter Winkler ( [e-mail]) is Professor of Mathematics and of Computer science and albert bradley third Century Professor in the sciences at dartmouth College, Hanover, nH.