0
$\begingroup$

How would you formulate and formally prove (from a minimal set of axioms) the following statement is true?

For all positive integers $n$, if $n+1$ items are placed into $n$ buckets, than one of the buckets must contain $2$ or more items.

  • 2
    From the standard axioms of the reals, my argument might go something like this: Assume not. Then each bucket has at most 1 item, implying that there are at most ($n$ buckets)(at most 1 item in each) = $n$ items. If that's all you were looking for, then this is called the finite pigeonhole principle, or the box principle, or the socks and drawers principle.2012-05-13

2 Answers 2

4

Induction will do it. If you have $n+1$ items in $n$ buckets, with no more than one item per bucket, remove one nonempty bucket along with the item in it to be left with the exact same situation with $n$ replaced by $n-1$. Clearly, the case $n=0$ is impossible.

  • 3
    I could have written it out more formally, but some work needs to be left to the asker of the question.2012-05-13
0

Assume that each bucket has at most 1 item. There are n buckets. So, n buckets have at most n items but that is a contradiction, since there are n+1 items in total.