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.)
Without loss of generality, we can assume that one of the six individuals N (say) has at least three friends, or N has at least three strangers.
If N has at least three strangers (say 1,2,3), then precisely one of the following will hold true:
(i) 1,2 and 3 are mutually friends.
(ii) 1,2 and 3 are mutually strangers.
(iii) At least two amongst 1,2 and 3 are mutual strangers.
We observe that for each of (i) and (ii), the conditions of the problem are trivially satisfied.
For (iii), the two mutual strangers (in relation to N) together with N constitute three mutual stangers and thus satisfy the given conditions.
It can be similarly proved that all the conditions of the problem will be satisfied if N has at least three friends.
Solution
