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
(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 webmaster.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: email@example.com