title: Covering dots on a Table
body: <p>In the Communications of the ACM, <a href="http://delivery.acm.org/10.1145/1790000/1787260/p128-winkler.html?key1=1787260&amp;key2=3588796821&amp;coll=portal&amp;dl=ACM&amp;CFID=108548737&amp;CFTOKEN=59330921" rel="nofollow">August 2008 "Puzzled" column</a>, Peter Winkler asked the following question:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>In the <a href="http://delivery.acm.org/10.1145/1820000/1810917/p110-winkler.html?key1=1810917&amp;key2=2298796821&amp;coll=portal&amp;dl=ACM&amp;CFID=108548737&amp;CFTOKEN=59330921" rel="nofollow">following issue</a>, he presented his proof:</p>
  
  <blockquote>
    <p>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.</p>
    
    <p>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 <code>sqrt(3)/3</code>, the hexagon
    itself has area <code>2*sqrt(3)</code>; since the
    hexagons tile the plane in a honeycomb
    pattern, the disks, each with area π,
    cover <code>π /(2*sqrt(3))</code> ~ .9069 of the
    plane's surface.</p>
    
    <p>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.)</p>
    
    <p>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.</p>
  </blockquote>
  
  <p>I don't understand. Doesn't the probabilistic nature of this proof simply mean that in the <strong>majority</strong> 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?</p>