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

Question

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.

Answer 1

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

\begin{equation} \sum_{1 \leqq i \leqq n} a_i \end{equation}

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

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

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.

Answer 2

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.