The Probabilistic Method

Four years ago, I took this class where we learned this cute method of solving certain kinds of math problems: the probabilistic method. I've already established my blog has no theme, so I guess this is right on theme.

The best way to explain this is to just give an example.

Let's say you have 10 points arranged in the x,y coordinate plane. You also have 10 unit circles. Are you able to cover all the dots without overlapping the coins?

It's not obvious (at least to me) how you'd prove this in a deterministic manner. Given a set of points, give exact instructions for how to arrange the circles? Thankfully, we can do something clever and employ the probabilistic method.

Tightly pack circles

Let's say we tightly pack circles like this and generate 10 random points. What's the probability one of the circles covers a point?

(Please try it out below. Click around a few times)

Assuming an infinite grid of circles arranged like that, the probability of a single point being covered is $90.69\%$.

Quick proof of that

This layout is essentially a bunch of equilateral triangles. Each equilateral triangle is covered the same amount. For simplicity, assume the radius of each circle = 1. Therefore, the triangle's side length is 2.

$A_{triangle} = \sqrt{3}$

Each triangle also contains 1/2 of a circle by area. (Three 60 degree slices of a circle) = $\frac{\pi}{2}$

Ratio = $\frac{A_{circle}}{A_{triangle}} = \frac{\pi}{2\sqrt{3}} \approx 0.9069$

Expected number of points covered

By linearity of expectation, the expected number of points covered is $10 \times 0.9069 = \boxed{9.069}$. To be clear, one point can only be covered by one circle, so if all 10 points are covered, we only keep the circles that happen to land on our points and discard the rest.

Probabilistic method

Here is the beautiful step of the probabilistic method. What does the expected number of points covered mean?

It means over the domain of all possible placements of the circles (i.e. shifting them to the left, right, up, down, etc.), the average number of points covered is 9.069.

Because the expected value is greater than 9, then the maximum number of points covered is also greater than 9. Because there are only integer values (e.g. you can't have 9.5 points covered), this means that there must exist at least one placement of the circles such that the number of points covered is 10.

$\blacksquare$