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.
I read the solution proof of the statement, but it didn't really seem to be derived or thought up easily - the idea behind the proof wasn't really intuitive to me.
Can anyone explain an easy to understand (intuitive) proof of the statement using the Pigeonhole Principle?
Here is a non-pigeonhole, but I think intuitive, proof. We say that a stone in a heap of size $k$ takes up $1/k$ of a heap. Suppose stone $i$ takes up $x_i$ of a heap in the first arrangement and $y_i$ of a heap in the second. Now we have $\sum_ix_i=4$, but $\sum_iy_i=5$, so $\sum_i(y_i-x_i)=1$. (This is where we assume the heaps are non-empty, so the sum over stones in each heap is $1$.)
Now for each $i$, $0<x_i,y_i\leq 1$. So $(y_i-x_i)<1$ for each $i$. So there must be at least two $i$ for which $(y_i-x_i)>0$. This corresponds to two stones which take up more of a heap than they did before, i.e. are in smaller heaps than they were before.