Ponder This Challenge - March 1999 - Cliques of people in a ballroom

Ponder This Challenge:

This month's problem is an easier one. Everyone deserves a break.

(Part A): There are 100 people in a ballroom. Every person knows at least 67 other people (and if I know you, then you know me). Prove that there is a set of four people in the room such that every two from the four know each other. (We will call such a set a "clique".)

(Part B): Two people in the room are Joe and Grace, who know
each other. Is there a clique of four people which includes Joe
and Grace?

(Part C): Oops, I miscounted. There are actually 101 people in
the room, But it's still true that each knows at least 67 others.
That can't make a difference, can it?

This problem was sent in by Mirek Wilmer.

FYI: Although this problem may appear simple at first, the
solution is actually fairly complex.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  (Part A): Pick a person arbitrarily, whom we will call Sam. Pick arbitrarily one of the people he knows; call her Julie. There are at most 33 people whom Sam does not know (including Sam himself), and at most 33 people whom Julie does not know, so among the 100 people in the room, at least 34 whom both Sam and Julie know; these 34 do not include Sam or Julie themselves.

  Pick one, say Bob. Argue the same way: among the 100 people in the room, at most 33 don't know Sam (including Sam himself), at most 33 don't know Julie, and at most 33 don't know Bob, so there is one person (Donna) known to all three. Then Sam, Julie, Bob and Donna form a clique.

  (Part B): Yes, by the same reasoning, because at the start of the process we picked the first person arbitrarily (and could pick Joe), and picked one of the people he knows arbitrarily (and could have picked Grace). Then continue as before.

  (Part C): Now there need not be a clique of four people. Suppose the 101 people are 33 freshmen, 34 sophomores and 34 juniors. Each person knows everyone in the other two classes but knows nobody in his own class. (It's a strange school.) Any set of four people would have to include two people from the same class, who don't know each other.

Solvers