Thread: Pigeonhole problem

I'm struggling with this problem for a while now, and I just can't figure it out.

Prove: Let
. If Objects are laid in t
Pigeonholes then there's at least one
so that the i-th pigeonhole has at least objects
in it

Try a proof by contradiction.

the idea is very simple. to "keep track", let's call the number of objects distributed in the i-th pigeonhole M_i.

first we check M₁, by counting the objects in the first pigeonhole. if M₁ ≥ n₁, we are done, it is the pigeonhole the theorem claims exists.

but maybe not. so we move on to M₂. if M₂ ≥ n₂, again, we are good, we can use M₂ as the desired pigeonhole.

but let's say it's just the worst possible case, the first t-1 pigeonholes all have fewer objects than the corresponding n_i.

how many objects do we have in all?

n₁ + n₂ +...+ n_t - t + 1.

what's the MOST possible objects we could have come across in our first t-1 pigeonholes?

(n₁ - 1) + (n₂ - 1) +...+ (n_t-1 - 1) = n₁ + n₂ +...+ n_t-1 - (t-1).

this means that there is at LEAST:

[n₁ + n₂ +...+ n_t - t + 1] - [n₁ + n₂ +...+ n_t-1 - (t-1)] = 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₁ + n₂ - 1 objects in 2 pigeonholes.

if the first pigeonhole has n₁ or more objects, we're done. if not, it has at most n₁ - 1. objects. that means there's at least n₂ objects left over which have to be in the 2nd pigeonhole.

the same logic applies to 3 pigeonholes and n₁ + n₂ + n₃ - 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₁+..+n_t - t + 1 = n₁+..+n_t - (t-1) 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₁+...+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").