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

Question

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

Report

Answer 1

Answers can be viewed only if

The questioner was satisfied and accepted the answer, or
The answer was disputed, but the judge evaluated it as 100% correct.

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.

Nirenberg

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

Answer

Related Questions

Search