The number of People who Know Each Other

Math Central

Quandaries & Queries

Question from Ted, a student:

I'm trying to prove that at a party where there are at least two people, there are two people who know the same number of other people there.

I'm able to plot out different scenarios, but how would I go about
proving this?

Ted,

Everybody knows some number between 0 and n-1 people. Is it possible that someone knows 0 and someone else knows n-1 at the same time?

Penny

Suppose there are N people.

Call the number of people somebody knows his "degree"

What is the smallest possible degree?

What is the largest possible degree (hint: it's not N (why?))

Why can you not have both of these at the same party?

So how many different degrees can you have at the same party?

And why must two people share one?

Good Hunting!
RD

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.