Note: This question has been posted on StackOverflow. I have moved it here because:
- I am curious about the answer
- The OP has not shown any interest in moving it himself
In the Communications of the ACM, August 2008 "Puzzled" column, Peter Winkler asked the following question:
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.
In the following issue, he presented his proof:
We had to show that any 10 dots on a table can be covered by non-overlapping $1 coins, in a problem devised by Naoki Inaba and sent to me by his friend, Hirokazu Iwasawa, both puzzle mavens in Japan.
The key is to note that packing disks arranged in a honeycomb pattern cover more than 90% of the plane. But how do we know they do? A disk of radius one fits inside a regular hexagon made up of six equilateral triangles of altitude one. Since each such triangle has area
sqrt(3)/3, the hexagon itself has area
2*sqrt(3); since the hexagons tile the plane in a honeycomb pattern, the disks, each with area π, cover
π /(2*sqrt(3))~ .9069 of the plane's surface.
It follows that if the disks are placed randomly on the plane, the probability that any particular point is covered is .9069. Therefore, if we randomly place lots of $1 coins (borrowed) on the table in a hexagonal pattern, on average, 9.069 of our 10 points will be covered, meaning at least some of the time all 10 will be covered. (We need at most only 10 coins so give back the rest.)
What does it mean that the disks cover 90.69% of the infinite plane? The easiest way to answer is to say, perhaps, that the percentage of any large square covered by the disks approaches this value as the square expands. What is "random" about the placement of the disks? One way to think it through is to fix any packing and any disk within it, then pick a point uniformly at random from the honeycomb hexagon containing the disk and move the disk so its center is at the chosen point.
I don't understand. Doesn't the probabilistic nature of this proof simply mean that in the majority of configurations, all 10 dots can be covered. Can't we still come up with a configuration involving 10 (or less) dots where one of the dots can't be covered?