I recently had an assignment and got this question wrong, was wondering what I left out.
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. Be sure to use the variable "n" when writing your answer.
My answer:
n >= 2
Case1: another person comes to the party, but doesn't know either of the first two. So the original two still only know the same number of people.
Case2: another person comes, and knows one out of the original 2, so therefore the >newcommer, and the one that doesnt know the newcommer both know the same number of people.
Case 3: another person comes and knows both of them, implying that they all know each >other, and therefore they all know the same number of people.So therefore if n>=2, where n and n-1 know each other, in either case whether n+1 joins, >there will be at least two people who know the same amount of people.
Many thanks in advance. Have a test coming up.
Best Answer
You are trying to prove this by induction, but it is not easy to do it that way. Say you had a party where two people each know four others. Now if a new guest arrives who knows one of them and not the other, you have broken the pair. You have to show that there is a pair in the new party.
I would approach it directly. If there are $n$ people at the party, each one knows somewhere from $0$ to $n-1$ of the others, which is $n$ possibilities. But if one person knows all the others, nobody knows nobody else (we are assuming knowing is reflexive here, otherwise the statement is not true-each person could know precisely those who arrived before him). So the number each person knows is either in the range $[0,n-2]$ or $[1,n-1]$. In either case, the pigeonhole principle says there are two that match.