Another nice puzzle from Peter Winkler on the momath website.
The puzzle: Given $10$ points on the 2D plane, can you cover them all with disjoint unit circles? i.e. Can you find a set of disjoint unit circles such that each of the $10$ points lie inside the circles?
.
.
.
.
Solution:
We give a probabilistic proof!
First consider that if we were asked to use a regular hexagon of side $s$ instead (and allowing them to touch only at the sides instead of full disjointedness), we could do it easily because we can tile the plane with a regular hexagon of any given size. We just tile the plane with regular hexagons of side $s$, translating/rotating etc if points happen to lie on the hexagon sides.
Now consider a regular hexagon, so that the radius of the inscribed circle inside the hexagon touching all its sides is $1$. The ratio of area of the circle to that of the hexagon comes out to be $\dfrac{\pi}{2\sqrt{3}} \approx 0.906 > 0.9$.
So basically the hexagon is a "good approximation" for the unit circle and we could try to use hexagons instead, hoping none of the points lie in the areas outside the unit circle. Now could translating etc work if a point happens to lie inside the unwanted area of the hexagon, that is not part of the circle?
This is where we can use the probabilistic method.
We are given the $10$ points. We now randomly tile the plane with regular hexagons whose inscribed circle is of radius slightly $ > 1$. We do this so that the unit circles centered at the centers of the hexagons can be disjoint. We can choose the side length so that the probability that any given point strictly lies inside the unit circle is still $\approx 0.906$.
Note that events are not independent (because the relative locations of the points are fixed), but by linearity of expectation, the expected number of points that lie strictly within the unit circles is $10 \times 0.906 > 9$. Thus there has to be some random arrangement of the hexagons where all the $10$ points lie inside the unit circles!
No comments:
Post a Comment