Brain Teasers
Knowing People at a Party
Prove that at any party, there are two people who know the same number of people. Assume that if A knows B , then B knows A . Assume also that everyone knows himself or herself.
Hint
Use indirect reasoning.Answer
Lets suppose that at a party, there are no two people who know the same number of people. Now lets say there are "n" people at the party. Now the nth person will know (n-1) people; (n-1)th person will know (n-2) people because no one knows the same number of people; similarly (n-2)th person will known (n-3) people. Thus, the 2nd person will know 1 person. Hence the 1st person[say A] will know 0 people or will know no one. Now since the nth person knows every one, he knows A .Therefore A knows the nth person. Hence our supposition is wrong and at least 2 people know the same number of people.Hide Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments hidden to avoid spoilers.
Follow Braingle!