# Proofs with the "Purified Pigeonhole Principle". [closed]

In his EWD980 and EWD1094, Dijkstra provides a formulation of the Pigeonhole Principle as such:

"For a non-empty, finite bag of numbers, the maximum value is at least the average (and the minimum is at most the average)"

One of the examples he provides where this is useful is in a proof of the following statement:

On a ranch, each cowboy is the exclusive owner of at least one horse. Show that the number of cowboys $$\leq$$ the number of horses.

The proof is simple if we realise that the minimum number of horses owned by a cowboy is one and thus the average number of horses owned by a cowboy is greater than or equal to 1, which gives the expression:

$$\frac{\text{number of horses}}{\text{number of cowboys}} \geq 1$$

I thought that this proof was quite neat and would like to ask if there are any other problems which can be solved quite elegantly using this "Purified" Pigeonhole Principle".

My intention is to source various examples whereby this formulation principle is used in an elegant manner, especially when the usual formulation makes the argument much more complicated.

• FYI I know this as the "third principle of PGP". (I believe I got that name from Koh Khee Meng's book, but I don't have it available as a reference.) $\quad$ Note that it's also true of real numbers (instead of just integers that PGP usually requires). Commented Jul 19 at 4:01
• EWD980, which you mention, is cs.utexas.edu/~EWD/transcriptions/EWD09xx/… and has a couple of examples. Commented Jul 19 at 7:30
• There is also an example at protocols.netlab.uky.edu/~calvert/classes/275/… Commented Jul 19 at 7:34
Solution: The optimal packing of the plane by disks–the hexagonal packing–has a packing density of about $$90.7\%$$. (The important fact is that this number is strictly larger than $$90\%$$.) So choose a random optimal packing. Then each of the $$10$$ points has about a $$9.3\%$$ chance of not being covered by the discs in this packing, so by the union bound there is at least about a $$7\% = 100 - 10(9.3)$$ chance that a random tiling covers the $$10$$ points. Since this chance is positive, there must be some tiling that covers all 10 points. For such a tiling, there are at most $$10$$ disks touching a point, so this is our solution.
To phrase it in terms of your "purified pigeonhole principle," let $$X$$ be a random variable that samples a random optimal tiling of the plane (equivalent to choosing a point in a hexagonal region uniformly at random for the center of one of the disks) and outputs $$1$$ if the corresponding tiling covers all $$10$$ points, $$0$$ otherwise. We've shown that $$E(X) > 0$$, therefore $$X = 1$$ with positive probability.