Covering eleven dots in the plane with eleven coins - counterexample?

333 Views Asked by At

The questions here and here relate to the question as to whether, given ten equally sized coins and a configuration of ten dots in the plane, there is a way of placing the coins so that they cover all the dots without overlapping.

The solution given depends on the fact that a close-packing of circles in the plane covers more than ninety percent of the area, and then uses probability to show that the expected number of dots covered by a random close-packing of coins is greater than nine, so some particular configuration must allow all ten dots to be covered.

But such an argument does not go through for eleven dots - and I was wondering if there were a counterexample in this case (or for some number greater than eleven). The margin is quite low for eleven, so a counterexample would have to be quite delicate.

1

There are 1 best solutions below

1
On BEST ANSWER

This is the Naoki Inaba coin-covering problem. The paper Covering Points with Disjoint Unit Disks shows a set of 45 points that can't be covered with unit disks. I believe that was beaten, but I don't recall the details.