Prove that if six people are riding together in an Evans Hall elevator, there is either a three-person subset of mutual friends (each knows the other two) or a three-person subset of mutual strangers (each knows neither of the other two).
Solution
1. Among any five people distinct from a fixed person \(P\), there are three who are all friends of \(P\), or three who are all strangers to \(P\).
Each of the other five people is either a friend of \(P\) or a stranger to \(P\). If at most two were friends and at most two were strangers, there would be at most four other people. Hence at least three belong to one of the two classes.
2. If \(P\) has three friends \(A,B,C\), then the six people contain either three mutual friends or three mutual strangers.
If some two of \(A,B,C\), say \(A\) and \(B\), are friends, then \[ \{P,A,B\} \] are three mutual friends, since both \(A\) and \(B\) are friends of \(P\).
Otherwise no two of \(A,B,C\) are friends. Then each pair among \(A,B,C\) consists of strangers, so \[ \{A,B,C\} \] are three mutual strangers.
3. If \(P\) has three strangers \(A,B,C\), then the six people contain either three mutual friends or three mutual strangers.
If some two of \(A,B,C\), say \(A\) and \(B\), are strangers, then \[ \{P,A,B\} \] are three mutual strangers, since both \(A\) and \(B\) are strangers to \(P\).
Otherwise no two of \(A,B,C\) are strangers. Then each pair among \(A,B,C\) consists of friends, so \[ \{A,B,C\} \] are three mutual friends.
4. Every set of six people contains three mutual friends or three mutual strangers.
Fix any one of the six people as \(P\). By step 1, either \(P\) has three friends among the other five or \(P\) has three strangers among them. Apply step 2 in the first case and step 3 in the second.
5. Q.E.D.
Step 4 is exactly the required conclusion.