Question

How do I prove the following:

In a room of 100 people, show that at least 3 people have the same number of acquaintances, where the number of acquaintances has to be even (including 0).

Answer 1

I came up with a solution:

Uses pigeonhole principle -

Case 1: Only one person has 0 friends, therefore taking that person out of the number of possible friends. Thus the remaining 99 people must have between 2, 4, 6, ... , 98 friends, i.e. 49 possibilities for for the 99 people. Since 2*49 + 1 = 99, there are at least 3 people with the same number of friends.

Case 2: Only 2 people have 0 friends (if I said three, the proof becomes trivial). The remaining 98 peopel have between 2, 4, 6, .... , 96 friends, i.e. 48 possibilities. Since 2*48 + 2 = 98, there are at least 3 people with the same number of friends.

Case 3: Everyone has at least 1 friend. But since everyone have to have an even number of friends, they have between 2 , 4 , 6, ... , 98 friends, i.e. 49 possibilities per person. Since 2*49+2 = 100, at least 3 people have the same number of friends.


Make sense?

Answer 2

I came up with a solution:

Uses pigeonhole principle -

Case 1: Only one person has 0 friends, therefore taking that person out of the number of possible friends. Thus the remaining 99 people must have between 2, 4, 6, ... , 98 friends, i.e. 49 possibilities for for the 99 people. Since 2*49 + 1 = 99, there are at least 3 people with the same number of friends.

Case 2: Only 2 people have 0 friends (if I said three, the proof becomes trivial). The remaining 98 peopel have between 2, 4, 6, .... , 96 friends, i.e. 48 possibilities. Since 2*48 + 2 = 98, there are at least 3 people with the same number of friends.

Case 3: Everyone has at least 1 friend. But since everyone have to have an even number of friends, they have between 2 , 4 , 6, ... , 98 friends, i.e. 49 possibilities per person. Since 2*49+2 = 100, at least 3 people have the same number of friends.


Make sense?

Answer 3

I came up with a solution:

Uses pigeonhole principle -

Case 1: Only one person has 0 friends, therefore taking that person out of the number of possible friends. Thus the remaining 99 people must have between 2, 4, 6, ... , 98 friends, i.e. 49 possibilities for for the 99 people. Since 2*49 + 1 = 99, there are at least 3 people with the same number of friends.

Case 2: Only 2 people have 0 friends (if I said three, the proof becomes trivial). The remaining 98 peopel have between 2, 4, 6, .... , 96 friends, i.e. 48 possibilities. Since 2*48 + 2 = 98, there are at least 3 people with the same number of friends.

Case 3: Everyone has at least 1 friend. But since everyone have to have an even number of friends, they have between 2 , 4 , 6, ... , 98 friends, i.e. 49 possibilities per person. Since 2*49+2 = 100, at least 3 people have the same number of friends.


Make sense?