The town of Friendville has an interesting property. Given any two people in the town, they either know each other or they don't. If they don't know each other, then they can be introduced to each other. One single introduction will work for both people. That is, "Tom this is Phil, Phil this is Tom" counts as one introduction.

The other interesting property that this town has, is that if any group of n people get together, the number of introductions that must be made in order that everyone in the group knows everyone else is at most n-1.

Problem: Prove that the town can be divided into two groups (A and B) such that everyone in group A knows each other, and everyone in group B knows each other.

This might be a better way of approaching it, while still keeping things simple:

(1) Start by separating out those townspeople who are universally known. Each chooses a red or blue rosette at random.
(2) Everyone else in the town must be a stranger to at least one other person. Choose A from this group, V at random and give him a blue rosette; now we are going to give a red rosette to everyone who doesn't know A, and doesn't already have a rosette, namely a,b,c,d...A doesn't know a, and A doesn't know b, so a and b know each other since otherwise A, a and b would be mutual strangers; we can reiterate the same argument to prove that a,b,c,d... are 'pairwise friends'.
(3) Next we give a blue rosette to everyone who doesn't know a, and doesn't already have a rosette, namely B,C,D,... Now, a doesn't know A, and a doesn't know B. A and B therefore know each other, since otherwise a,A, and B would be mutual strangers; and we can reiterate the same argument with A,a, and C, A, a, and D etc. to show that A,B,C,D... are 'pairwise friends'.
(4) We next give a red rosette to everyone who doesn't know B, and doesn't already have a rosette, namely ..e,f,g,h...We know that B doesn't know a, and B doesn't know e, so a and e are 'pairwise friends' and so on.
(5) Eventually we reach someone who was a stranger to b, but not a stranger to a, say, S. But then we can substitute b for a and use just the same method to show that b, c,...,s,t,u,v are likewise 'pairwise friends', and so continue until everyone has been assigned either a red or blue rosette. (Proof: (a) by definition, see (2) above; for every member, z, of V there exists at least one stranger able to assign a rosette to z; and (b) if z were a stranger to a,... then z would already have a rosette.
(7) It follows that if two people hold a rosette of the same colour, then this is sufficient to show they are friends. It is also necessary, for two people to be strangers, that they hold rosettes of opposite colours; but not sufficient, because they could also be friends.

Hence there are exactly 2 groups in the town of the required type.

 

Edited on June 22, 2013, 9:37 am

Posted by broll on 2013-06-16 13:14:42