Proving Two Partygoers Know Same # of People: A Proof

[bigplanet401]

Homework Statement

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.]

Homework Equations

Proof by contradiction.

The Attempt at a Solution

I started by trying to show that if no one knew the same number of people as anyone else, that that would lead to a contradiction. But I'm stuck even at this point. Any suggestions?

 

[RUber]

Assume there are N people, who all know different numbers of people.
then there is a person who knows the most people and a person who knows the fewest people.
What is the smallest number of people anyone could know?
What is the largest number of people anyone could know?
Arrange people in order of how many people they know.
Consider how the people could know each other, then see what happens when you get to the middle. I think the person who knows one less than half will necessarily be known by everyone in the top half.

 

[bigplanet401]

Each of the N members could know only themselves, or, in the extreme case, everyone could know everyone else (including themselves). I'm not sure what you mean by the "middle": are you assuming that one person knows only h/erself, one person knows 2 people,...,one person knows N people and that I should order accordingly?

 

[Dick]

Each of the N members could know only themselves, or, in the extreme case, everyone could know everyone else (including themselves). I'm not sure what you mean by the "middle": are you assuming that one person knows only h/erself, one person knows 2 people,...,one person knows N people and that I should order accordingly?

Sure. The only way that they can all be different is that 1 person knows only himself, one person knows 2 people, one person knows 3 people, etc until finally there is one person that knows everybody. What does that say about the one person that knows only himself?

 

[RUber]

If knowing yourself doesn't count, then you could have people knowing 0 to N-1, or 1 to N without initial contradiction.

 

[Dick]

If knowing yourself doesn't count, then you could have people knowing 0 to N-1, or 1 to N without initial contradiction.

But knowing yourself does count. The problem statement says that. You are suggesting a variation on the problem, right?

 

[RUber]

I missed that part in the initial problem.
I think the variation might be interesting to consider, but the same conclusion is reached since the maximum anyone would be able to know would be N-1.

 

[Dick]

I missed that part in the initial problem.
I think the variation might be interesting to consider, but the same conclusion is reached since the maximum anyone would be able to know would be N-1.

Sure. If somebody knows N-1 people (not counting themselves), then there is nobody that can know 0 people. It's just a different way of counting the people you know. It doesn't change the conclusion that two people must count the same number.

 

[bigplanet401]

Thanks for your help everyone...it makes a lot more sense now. The only way everyone knows a different number of people is if one person knows only h/erself, another person knows 2 people, ..., and one person knows everyone. But this would mean that the person who doesn't know anyone else in fact knows the socialite, which leads to a contradition, so at least two people must know the same number of people.