In Mutually friendly, we proved that if any two people are either friends or strangers, then any group of six people either contains 3 mutual friends or 3 mutual strangers, or both. Now, they can also be enemies.

Suppose that any two people are either friends, enemies, or strangers. Prove that any group of 17 people either contains 3 mutual friends, 3 mutual enemies, or 3 mutual strangers.

I just looked this up.  This is a problem addressed by "Ramsey's theorem" (look it up in Wikipedia).  The Ramsey number R(3,3,3) does in fact equal 17.  So 16 people will not guarantee it.

Posted by Steve Herman on 2011-07-02 22:18:46