IBM Research | Ponder This | March 1999 challenges
Skip to main content

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 webmaster.

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