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