Intereting Posts

$m,n>1$ are relatively prime integers , then are there at-least four idempotent (w.r.t. multiplication) elements in $\mathbb Z_{mn}$ ?
Determining the major/minor axes of an ellipse from general form
Limit involving a hypergeometric function
Is there a function with a removable discontinuity at every point?
What does “only” mean?
convergence of alternating series — weakening a hypothesis
Prove the class number of $\mathbb{Z}$ is $2$.
$S\subset \mathbb{R}^2$ with one and only one limit point in $\mathbb{R}^2$ such that no three points in $S$ are collinear
Optimization of relative entropy
An equivalent definition of uniform integrability
Does the sequence$ f_n(x)=\frac{x}{1+nx^2}$ converge uniformly on $\mathbb{R}$?
Expiring coupon collector's problem
Convergence or divergence of $\sum\limits_n(-1)^{\pi(n)}\frac1n$ where $\pi(n)$ is the number of primes less than or equal to $n$
Example of distinctions between multiple integral and iterated integrals.
Finding number of ways of selecting 6 gloves each of different colour from 18 gloves?

**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:

- Are there any open mathematical puzzles?
- Distribution of points on a rectangle
- Find the poisoned pie
- Why are these geometric problems so hard?
- Optimization with a Probability
- Time-and-Work and Motorcycle Tyres

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?

- Random Walk of a drunk man
- Fibonacci numbers from $998999$
- A logic puzzle involving a balance.
- Rainbow Hats Puzzle
- Chicken Problem from Terry Tao's blog (system of Diophantine equations)
- Any smart ideas on finding the area of this shaded region?
- Enigma : of Wizards, Dwarves and Hats
- Chameleons of Three Colors puzzle

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.

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).

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 🙂

- If an $H\le G$ has an irreducible representation of dimension $d$, then show $G$ has an irreducible representation of at least dimension $d$.
- Independence of disjoint events
- Groups where all elements are order 3
- How do you derive the continuous analog of the discrete sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, …$?
- How to solve Real Analysis
- Prove that for $n \ge 3$, for any integer $w$, $\exists x$ such that $w < x < w + p_n\#$ and lpf$(x) \ge p_{n+3}$
- Krull dimension and transcendence degree
- If $a^2 + b^2 + c^2 = 2$, find the maximum of $\prod(a^5+b^5)$
- How does one compute a bounding simplex for a set of points?
- Summation of $\sum\limits_{n=1}^{\infty} \frac{x(x+1) \cdots (x+n-1)}{y(y+1) \cdots (y+n-1)}$
- Proof of Proposition/Theorem V in Gödel's 1931 paper?
- Sobolev spaces fourier norm equivalence
- Why in an inconsistent axiom system every statement is true? (For Dummies)
- Martingale and Submartingale problem
- Constructing an explicit isomorphism between finite extensions of finite fields