Hint: Choose a person, P1, to start with. The set of friends of P1 can be denoted F1 and the set of non-friends N1. One of these two sets is infinite. (Possibly both are infinite.) Let S1=F1 if that set is infinite. Otherwise let S1 be N1. Suppose that {P1,P2,...,Pn} and {S1,...,Sn} have been defined. Let Pn+1 be a person in Sn. Let Sn+1 be the set of people in Sn which are friends with Pn+1 if that set is infinite. Otherwise, let Sn+1 be the set of people in Sn which are not friends with Pn+1.

In the end you get an infinite sequence of people {Pi}, but they are not the set you want. What do you do now?

Complete Solution