Covering 10 dots on a table with 10 equivalent - sized coins: description of evidence

Note: This question has been posted on StackOverflow. I have actually relocate below due to the fact that:

  1. I wonder concerning the solution
  2. The OP has actually disappointed any kind of passion in relocate himself

In the Communications of the ACM, August 2008 "Puzzled" column, Peter Winkler asked the adhering to inquiry:

On the table prior to us are 10 dots, and also in our pocket are 10 $1 coins. Confirm the coins can be positioned on the table (no 2 overlapping) as if all dots are covered. Number 2 reveals a legitimate positioning of the coins for this certain set of dots ; they are clear so we can see them. The 3 coins near the bottom are not required.

In the following issue, he offered his evidence:

We needed to show that any kind of 10 dots on a table can be covered by non - overlapping $1 coins, in a trouble designed by Naoki Inaba and also sent out to me by his close friend, Hirokazu Iwasawa, both puzzle wizards in Japan.

The key is to keep in mind that packaging disks prepared in a honeycomb pattern cover greater than 90% of the aircraft. Yet just how do we understand they do? A disk of distance one fits inside a normal hexagon composed of 6 equilateral triangulars of elevation one. Given that each such triangular has location $\frac{\sqrt{3}}{3}$, the hexagon itself has location $2 \sqrt{3}$ ; given that the hexagons floor tile the aircraft in a honeycomb pattern, the disks, each with location $\pi$, cover $\frac{\pi}{2\sqrt{3}}\approx .9069$ of the aircraft is surface area.

It adheres to that if the disks are positioned arbitrarily on the aircraft, the probability that any kind of certain factor is covered is.9069. Consequently, if we arbitrarily position great deals of $1 coins (obtained) on the table in a hexagonal pattern, generally, 9.069 of our 10 factors will certainly be covered, suggesting at the very least several of the moment all 10 will certainly be covered. (We require at the majority of just 10 coins so repay the remainder.)

What does it suggest that the disks cover 90.69% of the boundless aircraft? The most convenient means to address is to claim, probably, that the percent of any kind of huge square covered by the disks approaches this value as the square expands. What is "arbitrary" concerning the positioning of the disks? One means to assume it via is to deal with any kind of packaging and also any kind of disk within it, after that select a factor evenly randomly from the honeycomb hexagon having the disk and also relocate the disk so its facility goes to the picked factor.

I do not recognize. Does not the probabilistic nature of this evidence merely suggest that in the bulk of arrangements, all 10 dots can be covered. Can not we still think of an arrangement entailing 10 (or much less) dots where among the dots can not be covered?

2019-05-18 23:58:30
Source Share
Answers: 3

The bottom line is that the 90.69% probability is relative to "the disks [being ] positioned arbitrarily on the aircraft", not the factors being positioned arbitrarily on the aircraft. That is, the set of factors on the aircraft is dealt with , yet the honeycomb setup of the disks is positioned over it at an arbitrary variation. Given that the probability that any kind of such positioning covers an offered factor is 0.9069, an arbitrary positioning of the honeycomb will certainly cover, generally, 9.069 factors (this adheres to from linearity of assumption ; I can expand on this if you like). Currently the only means arbitrary positionings can cover 9.069 factors generally is if some of these positionings cover 10 factors - - if all positionings covered 9 factors or much less, the ordinary variety of factors covered would certainly go to the majority of 9. Consequently, there exists a positioning of the honeycomb setup that covers 10 factors (though this evidence does not inform you what it is, or just how to locate it).

2019-05-21 12:05:57

Nice! The above evidence confirms that any kind of arrangement of 10 dots can be covered. What you have below is an instance of the probabilistic method, which makes use of probability yet offers a particular (not a probabilistic) verdict (an instance of probabilistic proofs of non-probabilistic theorems). This evidence additionally unconditionally makes use of the linearity of assumption, a reality that appear counter - instinctive in many cases till you get made use of to it.

To make clear the evidence: offered any kind of arrangement of 10 dots, deal with the arrangement, and also take into consideration positioning honeycomb - pattern disks arbitrarily. Currently, what is the predicted number $X$ of dots covered? Allow $X_i$ be 1 if dot $i$ is covered, and also $0$ or else. We understand that $E[X] = E[X_1] + \dots + E[X_{10}]$, as well as additionally that $E[X_i] = \Pr(X_i = 1) \approx 0.9069$ as clarified over, for all $i$. So $E[X] = 9.069$. (Note that we have actually gotten this outcome making use of linearity of assumption, despite the fact that it would certainly be tough to say concerning the occasions of covering the dots being independent.)

Currently, given that the standard over positionings of the disks (for the dealt with arrangement of factors!) is 9.069, not all positionings can cover ≤ 9 dots-- at the very least one positioning has to cover all 10 dots.

2019-05-21 12:04:40

If you read meticulously, this evidence is for an approximate positioning of dots. So offered any kind of dot setup, if we simply position the coins arbitrarily (in the honeycomb setup,) after that generally we will certainly cover a little greater than 9 of the dots. Yet given that we can not cover "component" of a dot (in this trouble) then that suggests that there exists an arbitrary positioning of the coins that covers all 10 dots. So despite the arrangement of dots, we understand that there is constantly a means to cover the dots with at the majority of 10 coins

2019-05-21 09:54:50