# Prove that the Pigeonhole Principle is equivalent to "the max is at least the average".

I can see that the statement "Let $$A$$ be a finite, nonempty set of real numbers, with average $$\overline A$$. Then $$\max A \ge \overline A$$." has something about it that seems like the Pigeonhole Principle. But I can't quite see how to prove that the Pigeonhole Principle implies this.

I can give a pretty obvious independent proof. Let $$|A|=n$$ so that in general we have $$n\overline A = \sum_{x\in A}x$$ For contradiction suppose all the numbers in $$A$$ are less than the average. Then $$n\overline A > \sum_{x \in A}x$$, a contradiction with the above.

But I'm not seeing how to give a proof that makes essential use of the Pigeonhole Principle. I thought about how the average partitions the real line into three pigeonholes: Points above, on, or below the average. For this to be relevant we'd need a set with at least 4 elements, so maybe we handle sets with 3 or fewer as special cases. But even if $$A$$ has 4 elements, we don't learn much by stating that some two go to the same partition.

Maybe we instead think about how the maximum partitions the real line ... but that doesn't seem to make much sense. Maybe we consider the first $$n-1$$ elements and use its average or something like that ... I'm not seeing how to make use of that idea.

• Since the pigeonhole principle is only about integers, it is easier to prove this for rational numbers from the PH rather than reals. Then you can extend it to all reals by continuity. Commented Jul 15, 2022 at 18:10
• I can go the other way (max>avg implies PH): if the average number of pigeons is more than 1, then so must the maximum Commented Jul 15, 2022 at 18:13
• But the traditional approach, without PH, is easier. It essentially amounts to if $a,b$ are real numbers, and $t\in[0,1]$ then $$\min(a,b)\leq ta+(1-t)b\leq \max(a,b).$$ The proof then follows by induction, since $$\frac{x_1+\cdots+x_n}n=\frac{n-1}n\frac{x_1+\cdots x_{n-1}}{n-1}+\frac1nx_n.$$ Commented Jul 15, 2022 at 18:17
• @ThomasAndrews That seems a bit more complicated than the proof already contained in the OP. Commented Jul 15, 2022 at 18:20
• @anomaly No, although I have see that paper referenced. I was reading West's book Combinatorial Mathematics where similar things are discussed, and did a bunch of googling, and have seen in several places the claim (or the homework assignment) to prove that the PHP proves this. Commented Jul 15, 2022 at 18:50

Here's a slightly different way of proving it which I found a little more intuitive (I'm not sure it's possible to prove the statement for real numbers using the Pigeonhole principle). I show this for the natural numbers, but the same principle (without the wooden blocks analogy) can be applied to the integers. This explanation comes from my notes.

Let $$A$$ be a set with $$n$$ members (which are all natural numbers). We can label the members of $$A$$ as $$a_1, a_2, ..., a_n$$. Let us partition the elements of $$A$$ into $$n$$ boxes (this isn't hard, as we have $$n$$ elements, so we just put one element in each box). How does this help us? Sure, we have technically applied the pigeonhole principle (as we have placed $$n$$ objects into $$n$$ boxes, such that by the Pigeonhole Principle there is at least $$1$$ element in each box - not particularly helpful) but we haven't proven our statement. To actually prove the statement, we can combine this partitioning of our objects with a different way of considering them; let us combine them into one big number. We know that the total value of all the elements in our set is

$$$$\sum_{1 \leqq i \leqq n} a_i$$$$

Now we return to nursery! You have probably played with wooden blocks, and seen how if we start with a single wooden block, we can say this represents the number $$1$$. If we have two equally shaped wooden blocks, we can say this represents $$2$$, and so on. In the general case if we have $$y$$ wooden blocks, we can build the number $$y$$. The reverse also applies; by this line of "reasoning" we can split the number $$\sum_{1 \leqq i \leqq n} a_i$$ into $$\sum_{1 \leqq i \leqq n} a_i$$ wooden blocks. If we then partition these blocks into $$n$$ sets, for any possible partitioning we will have at least $$x$$ objects in one set, where

$$$$x = \left\lceil \frac{\sum_{1 \leqq i \leqq n} a_i}{n} \right\rceil$$$$

Or, alternatively, we will have a number which is at least as big as $$x$$. We also know that the earlier partition of $$a_1, a_2, ..., a_n$$ into $$n$$ sets will satisfy this property. Therefore, there exists at least one $$k$$ such that

\begin{align} a_k &\geqq \left\lceil \frac{\sum_{1 \leqq i \leqq n} a_i}{n} \right\rceil \\ &\geqq \frac{\sum_{1 \leqq i \leqq n} a_i}{n} \tag{A} \label{the average of set A} \end{align}

Note that the expression Equation $$\ref{the average of set A}$$ is equivalent (by definition) to the average of the elements of $$A$$, and thus there exists an element greater than or equal to the average.

• Excellent proof! I'll have to think later about how to generalize to reals, but this is wonderful. I'm considering perhaps something along the lines of "this is an equality of two functions which are in agreement at all natural numbers; therefore extending the function to the reals in a natural way, these too will be in agreement at all real points". There's a good chance that won't work, but I'll have to wait until winter break to think more about it. Also, your notes look very interesting! Commented Oct 21, 2022 at 20:19
• Great proof. The link you have in your post works but the internal hyperlinks to the specific notes do not (there is an extra /html/ put in the link so it just goes nowhere). Here is the link to the pigeonhole principle proof/notes mentioned which works: notes.reasoning.page/Ch6.S5 Commented Apr 19 at 17:56

Here is the same proof but using more explicit pigeonholes. So given some non-negative numbers $$a_1,a_2,...,a_n$$ and I give you a segment of length $$n\overline{A}$$ and ask you to break it into $$n$$ pieces that are of length $$a_1, a_2,..., a_n$$. Now divide the segment into $$n$$ pieces of size $$\overline{A}$$ and note that if some $$a_k$$ is less than average this means it will be shorter than $$\overline{A}$$. Now if all of the $$a_k$$ are less than average this means when we match up each $$a_k$$ to the segment of length $$\overline{A}$$ that all of them will have some excess, which is to say that $$\overline{A}-a_k > 0$$, so when you break off all the excess pieces you'll have some non-zero length of the segment left without another $$a_{n+1}$$ to match it up with, so we have more pigeons than holes.

To include the negative numbers we can say that if $$a_k < 0$$ it's equivilent to giving you $$\vert a_k \vert$$ more segment to place rather than a piece to be placed on.

• Just to be explicit, we are taking $a_i$ to be nonnegative so that we can interpret it as length. And presumably once the theorem is proved for nonnegative reals, we can maybe use that to prove it for negatives. Commented Jul 15, 2022 at 18:52
• @Addem good point. We can interpret negative $a_k$ as giving you $\vert a_k \vert$ more segment though so it's not too hard to patch it. Commented Jul 15, 2022 at 19:06