$Two persons with the same number of acquaintance in a party$

Question

$Two persons with the same number of acquaintance in a party$

There are $n$ persons attending a party. Prove that there are two persons who have the same number of acquaintance among the people attending the party.

Math Competitions Putnam Competition Calculus

Elviegem

41

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

There are $n$ persons attending the party and their numner of acquaintances could be
\[ 0,1,2, \cdots (n-1). \]
There are a total of nn numbers in the above list. However, it is not possible to have a person with 1 acquaintance and $(n−1) $acquaintances at the same time. So the total number of possible acquaintances is $(n-1)$ while $n$ persons are attending the party. By Pigeonhole Principle there must be two persons with the same number of acquaintances.

Erdos

4.8K

$Two persons with the same number of acquaintance in a party$

Answer

Related Questions

Search