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.
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.
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.
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.