Prove that any group of six people contains either 3 mutual friends or 3 mutual strangers.

(For the purpose of this problem any pair of people must be either friends or strangers.)

first split the group up into possible combinations:
6 and 0
5 and 1
4 and 2
3 and 3
considering these combinations, it is not possible to get a combination with both numbers less than 3, so no matter what there will be at least 3 mutual friends or 3 mutual strangers

Posted by calla tah-n on 2003-05-22 20:53:54