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.
Frankly, it took me several minutes to even understand what they meant by 'at least two stones are placed into a smaller heap', because I pictured just moving 1 stone from the 4 old heaps and creating, all by itself, a fifth heap, so I figured as such we would only be placing 1 stone into a smaller heap.
But I think I understand: when I move the 1 stone, then all the other stones remaining in the old heap where I took the 1 stone from are now in a heap that is 1 smaller than it was and, as such, they are also 'placed into a smaller heap'. Which means there are indeed two or more.
So, what they mean is: if you have 4 heaps of stones, and make those into 5 heaps of stones, then there will be at least two stones that end up in a heap that is smaller than the size of the heap that they were in.
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.