# Pigeon Holes Question

• Dec 5th 2009, 02:54 PM
discretec
Pigeon Holes Question
I am stuck on this question involving the pigeon hole principle. Any help is appreciated.
In a gathering of 30 people, there are 104 different pairs of people who know each other.
a. Show that some person must have at least seven acquaintances.
b. Show that some person must have fewer than seven acquaintances.

I think this one uses the ceiling function, but I am confused.
• Dec 5th 2009, 03:13 PM
galactus
Part a, 208/30=7. See?.
• Dec 5th 2009, 03:17 PM
discretec
Quote:

Originally Posted by galactus
Part a, 208/30=7. See?.

I feel really stupid now. Thank you. I must be tired.(Doh)
• Dec 5th 2009, 03:22 PM
galactus
For part b, maybe try a contradiction argument of some sort. Often, that is a good approach when doing a PHP proof.

Maybe show there is a contradiction by there being at least 105 pairs of acquaintances. That may be one way to approach it.

• Dec 5th 2009, 03:29 PM
Plato
Quote:

Originally Posted by galactus
For part b, maybe try a contradiction argument of some sort. Often, that is a good approach when doing a PHP proof.

Maybe show there is a contradiction by there being at least 105 pairs of acquaintances. That may be one way to approach it.

Actually the pigeons are the acquaintances and there are 208.
Each pair contributes two acquaintances. The holes are the persons.