# Arranging 4 Piles into 5 Piles - Pigeonhole Principle [Continued]

I read the following exercise in my combinatorics book in the section on the Pigeonhole Principle.

There are four heaps of stones in our backyard. We rearrange them into five heaps. Prove that at least two stones are placed into a smaller heap.

and this is the proof that I read:

I'm having a hard time understanding the intuition and reasonining/logic in this proof, mainly after the $a_k > b_k$ step. I'm having difficulty seeing why we need the following inequality and how the conclusion follows from it.

I would appreciate any explanation or elaboration on this proof in helping to understand.

• Apparently it is assumed a "heap" (or pile, if you prefer) cannot be empty. Otherwise we could put all stones (if any!) in the original four heaps into a single combined heap and count four additional empty heaps as giving a total of five heaps. In this way no stone would be placed into a heap smaller than the one it original appeared in. Commented Jun 20, 2017 at 23:16

Now, as far as their argument goes: we have of course that $a_1+a_2+a_3+a_4=b_1+b_2+b_3+b_4+b_5$, with each of these $\ge 1$, and so indeed $a_1+a_2+a_3+a_4>b_1+b_2+b_3+b_4$. Now, it could be that $b_1>a_1$, or that $b_2>a_2$, or that $b_4>a_4$, but it has to be the case that there is a smallest $k$ for which $a_1+...+a_k>b_1+...b_k$. And since this is the smallest $k$, it has to be the case that $a_k>b_k$, for if $a_k \le b_k$, then $a_1...a_{k-1}>b_1...b_{k-1}$, and hence $k$ would not have been the smallest index to get our inequality.
Now, consider all the stones in piles $a_1$ through $a_k$. In order for them to not end up in smaller heaps, they need to be put into piles $b_1$ through $b_{k-1}$, since al these piles are bigger than $b_k$. But that leaves $a_1+...+a_k-b_1-...-b_{k-1} > b_k$ stones, and since $b_k \ge 1$, that means that at least two stones cannot be put in piles $b_1$ through $b_{k-1}$, so at least two stones from the piles $a_1$ through $a_k$ must have ended up in piles of size $b_k$ or smaller, thus proving the claim.