2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Commented Jun 20, 2017 at 23:16

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .