IBM Research | Ponder This | March 1999 challenges

Ponder This

March 1999

<<February March April>>

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

Challenge: 03/01/99 @ 12:00 AM EST
Solution: 04/01/99 @ 12:00 AM EST
List Updated: 04/01/99 @ 12:00 AM EST