Knowing People at a Party
Date: 08/27/98 at 01:56:53 From: Maylyn Angeles Subject: Indirect reasoning 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. It's been suggested that I use indirect reasoning.
Date: 08/27/98 at 05:15:15 From: Doctor Floor Subject: Re: Indirect reasoning Hi Maylyn, Thank you for sending your question to Dr. Math. Let's say that there are N people at the party. For indirect reasoning, assume that all these people know different numbers of people at the party. Then there must be one who knows 1, one who knows 2, one who knows 3, ..., and one who knows N. This fits exactly for N people. Although this is the only possibility, I am going to show that it is impossible that one person knows 1 (must be himself) and one person knows N. If it is impossible, then it is also impossible to have all different numbers of people known. So we have shown by indirect reasoning that there must be two people who know the same number of people. We derived that there must be one person who only knows himself (or herself), and one person who knows everybody - but then the person who knows everybody also knows the person who only knows himself, and we assumed that if A knows B, then B knows A. This means that the person who was thought only to know himself also knows somebody else. It is not possible that one person knows only himself, and one person knows everybody, so we're done. If you have a math question again, please send it to Dr. Math. Best regards, - Doctor Floor, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.