Popularized by Paul Erdős, the probabilistic method proves the existence of combinatorial objects by showing that a randomly chosen object has the desired property with positive probability. Here, we look at a particularly clean pedagogical example1:
We visualize several randomly generated configurations, together with one valid cut for each, in the figure above.2 Before reading on, it is worth pausing to think about how one might complete this proof.
A Probabilistic Proof
The key idea in the following proof is to randomize the cut. Choose a horizontal line by sampling its height uniformly from \([0,1]\). How many circles does it intersects on average?
For each circle \(i\), define the indicator random variable
\[X_i = \begin{cases} 1, & \text{if the cut passes through circle } i, \\ 0, & \text{otherwise}. \end{cases}\]Then define
\[X = \sum_{i=1}^{m} X_i.\]The random variable \(X\) is the total number of circles intersected by the cut. To show that the desired cut exists, it is enough to prove that
\[\mathbb{E}[X] > 3,\]because an integer-valued random variable can have expectation greater than \(3\) only if
\[\Pr(X \geq 4) > 0.\]By linearity of expectation,
\[\begin{aligned} \mathbb{E}[X] &= \mathbb{E}\left[\sum_{i=1}^{m} X_i\right] \\ &= \sum_{i=1}^{m} \mathbb{E}[X_i] \\ &= \sum_{i=1}^{m} \Pr(X_i = 1), \end{aligned}\]where the last equality uses the defining property of an indicator random variable.
If circle \(i\) has radius \(r_i\), a horizontal line intersects it precisely when the sampled height falls within an interval of length \(2r_i\). Thus \(\Pr(X_i=1)=2r_i\). Writing \(C_i=2\pi r_i\) for its circumference, we get
\[\begin{aligned} \mathbb{E}[X] &= \sum_{i=1}^{m} 2r_i \\ &= \sum_{i=1}^{m} \frac{C_i}{\pi} \\ &= \frac{10}{\pi} \\ &\approx 3.183 > 3. \end{aligned}\]Therefore some horizontal cut intersects at least four circles.3
Simple, but cute, isn’t it?
-
I came across this proof in a class in 2015, but the problem itself dates back at least to Arthur Engel’s Problem-Solving Strategies (1998). ↩
-
There must be at least four circles: three circles contained in the unit square can have total circumference at most \(3\pi < 10\). ↩
-
At this point, it is quite clear the underlying reason that the cut exist is the “pigeonhole principle”. ↩