Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/