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
Math Forum Home || Math Library || Quick Reference || Math Forum Search