March 1999
<<February March April>>
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
People who answered correctly:
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.