# Thread: [SOLVED] Application of the Pigeonhole Principle

1. ## [SOLVED] Application of the Pigeonhole Principle

I have some problems relating to the pigeonhole principle. Here they are:

Prove that at a party where there are at least two people, there are two people who know the same number of other people there.

The other one is,

Let n1, n2, ... , nt be positive integers. Show that if n1+n2+...+nt - t + 1 objects are placed into t boxes, then for some i, i = 1, 2, ... , t, the ith box contains at least ni objects.

Now, I was given the hint that the pigeonhole principle can help me here, but I don't know how to apply it. Are there any other hints anyone could think of to help me prove this? Thanks.

2. Originally Posted by Oijl
Prove that at a party where there are at least two people, there are two people who know the same number of other people there.
We must make some assumptions here.
First “If A knows B then B knows A”.
Second “A knows at most $n-1$ other people at the party".

This problem is equivalent to the theorem: In a simple graph at two vertices have the same degree.

For the pigeonholes, there $n$ of them: $0,1,\cdots,n-1$.
Anyone at the party can know from $0$ to $n-1$ other people.

Suppose that none of those pigeonholes has more than one person in it.
Convince yourself that the $[n-1]^{th}$ hole would be empty.

3. Not to be rude, but I think simply applying the fact that we have $n-1$ holes as you described, and n people in the party, the pidgeonhole principle directly gives us that there must be two people in at least one hole.

4. Originally Posted by Defunkt
Not to be rude, but I think simply applying the fact that we have $n-1$ holes as you described, and n people in the party, the pidgeonhole principle directly gives us that there must be two people in at least one hole.
That is not being rude. It is being unable to count.
There are $n$ holes: $0,1,\cdots,n-1$.

5. Oops, didn't see the 0. Sorry.

6. I see! All the pigeonholes cannot be filled, because that is a contradiction, because the hole representing zero cannot be filled while the hole representing knowing n - 1 is filled... and since there are the same number of elements as holes, and all the holes cannot be filled, there must be some hole with more than one element in it.

,

,

,

### let n1, n2,....nt be positive integer show that if n1 n2 ..nt-t.v., the objects are placed into t boxes, then for some I, i=1,2,....t, the I th box contains at least n:objects

Click on a term to search for related topics.