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.
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.
There are $n$ holes: $0,1,\cdots,n-1$.