Covering ten dots on a table with ten equal-sized coins: explanation of proof 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 $\frac{\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 $\pi$,
  cover $\frac{\pi}{2\sqrt{3}}\approx .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?
 A: If you read carefully, this proof is for an arbitrary placement of dots. So given any dot arrangement, if we just place the coins randomly (in the honeycomb arrangement,) then on average we will cover slightly more than 9 of the dots. But since we can't cover "part" of a dot (in this problem) then that means that there exists a random placement of the coins that covers all 10 dots. So no matter the configuration of dots, we know that there is always a way to cover the dots with at most 10 coins :) 
A: Nice! The above proof proves that any configuration of 10 dots can be covered. What you have here is an example of the probabilistic method, which uses probability but gives a certain (not a probabilistic) conclusion (an example of probabilistic proofs of non-probabilistic theorems). This proof also implicitly uses the linearity of expectation, a fact that seem counter-intuitive in some cases until you get used to it.
To clarify the proof: given any configuration of 10 dots, fix the configuration, and consider placing honeycomb-pattern disks randomly. Now, what is the expected number $X$ of dots covered? Let $X_i$ be 1 if dot $i$ is covered, and $0$ otherwise. We know that $E[X] = E[X_1] + \dots + E[X_{10}]$, and also that $E[X_i] = \Pr(X_i = 1) \approx 0.9069$ as explained above, for all $i$. So $E[X] = 9.069$. (Note that we have obtained this result using linearity of expectation, even though it would be hard to argue about the events of covering the dots being independent.)
Now, since the average over placements of the disks (for the fixed configuration of points!) is 9.069, not all placements can cover ≤9 dots — at least one placement must cover all 10 dots.
A: The key point is that the 90.69% probability is with respect to "the disks [being] placed randomly on the plane", not the points being placed randomly on the plane. That is, the set of points on the plane is fixed, but the honeycomb arrangement of the disks is placed over it at a random displacement. Since the probability that any such placement covers a given point is 0.9069, a random placement of the honeycomb will cover, on average, 9.069 points (this follows from linearity of expectation; I can expand on this if you like). Now the only way random placements can cover 9.069 points on average is if some of these placements cover 10 points -- if all placements covered 9 points or less, the average number of points covered would be at most 9. Therefore, there exists a placement of the honeycomb arrangement that covers 10 points (though this proof doesn't tell you what it is, or how to find it).
