
Pigeonhole problem
I'm struggling with this problem for a while now, and I just can't figure it out.
Prove: Let $\displaystyle n_1, n_2, . . . , n_t \in N^+$
. If $\displaystyle n_1 + n_2 + . . . + n_tt + 1$ Objects are laid in t
Pigeonholes then there's at least one $\displaystyle i \in \{1, . . ., t\}$
so that the ith pigeonhole has at least $\displaystyle n_i$ objects
in it

Re: Pigeonhole problem
Try a proof by contradiction.

Re: Pigeonhole problem
the idea is very simple. to "keep track", let's call the number of objects distributed in the ith pigeonhole M_{i}.
first we check M_{1}, by counting the objects in the first pigeonhole. if M_{1} ≥ n_{1}, we are done, it is the pigeonhole the theorem claims exists.
but maybe not. so we move on to M_{2}. if M_{2} ≥ n_{2}, again, we are good, we can use M_{2} as the desired pigeonhole.
but let's say it's just the worst possible case, the first t1 pigeonholes all have fewer objects than the corresponding n_{i}.
how many objects do we have in all?
n_{1} + n_{2} +...+ n_{t}  t + 1.
what's the MOST possible objects we could have come across in our first t1 pigeonholes?
(n_{1}  1) + (n_{2}  1) +...+ (n_{t1}  1) = n_{1} + n_{2} +...+ n_{t1}  (t1).
this means that there is at LEAST:
[n_{1} + n_{2} +...+ n_{t}  t + 1]  [n_{1} + n_{2} +...+ n_{t1}  (t1)] = n_{t} objects in the last pigeonhole.
*********************
it's easier to see what is happening with a small number of pigeonholes.
suppose we have only one, and we have k objects distributed in 1 pigeonhole. then that pigeonhole has at least k objects (duh!).
perhaps that's "too easy". ok, let's try TWO pigeonholes, with n_{1} + n_{2}  1 objects in 2 pigeonholes.
if the first pigeonhole has n_{1} or more objects, we're done. if not, it has at most n_{1}  1. objects. that means there's at least n_{2} objects left over which have to be in the 2nd pigeonhole.
the same logic applies to 3 pigeonholes and n_{1} + n_{2} + n_{3}  2 objects. rather than go through the same steps, let's pick 3 numbers, like 3,6, and 8. 3+6+8 = 17. 17  2 = 15.
so we have 15 objects to place in 3 pigeonholes. can we "beat the theorem" by placing less than:
3 objects in the first pigeonhole (ok, we want to get rid of "as many as we can" so we put 2. now we have 13 left).
6 objects in the 2nd pigeonhole (the most we can put is 5, right? that leaves us with...uh...8 left).
8 objects in the 3rd pigeonhole (well, shucks...we're stuck!)?
do you see why the theorem claims we have n_{1}+..+n_{t}  t + 1 = n_{1}+..+n_{t}  (t1) objects?
if we had subtracted from the sum of the n_{i}, t objects, it would be possible to put n_{i}1 objects in each pigeonhole, summing to a total of n_{1}+...+n_{t}  t objects.
by only subtracting t  1 objects, we ensure at least ONE pigeonhole has n_{i} objects (the "extra one we didn't subtract").