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.

Start with a putative group of n=3 people who do not know each other.

The greetings:

'A this is B, B this is A';
'A this is C, C this is A',
'B this is C, C this is B',

require three introductions.

But this is one more than permitted by the stipulation of the problem that 'the number of introductions that must be made in order that everyone in the group knows everyone else is at most n-1' i.e. 2 introductions.

So at least two of A,B,C must know each other, and this must be true for any group of 3 chosen. Assume that A and C are friends in the A group, and place B, who does not know A, in the B group. Whether B and C are acquainted is irrelevant. Now we take the next townsperson, D, and put them with A and B. A and B don't know each other, so D knows A, or D knows B. He must therefore be in either the A group, or the B group; having assigned D appropriately, we repeat the same process until every townsperson has been allocated to one of the groups. Hence the desired property is shown.

Notes:
(1) If all 3 know each other, keep selecting new townspeople until one is a stranger to one of the other two, producing the position already described.

(2) If all the townspeople know each other, then any division of their number will produce the required groups.

Edited on June 15, 2013, 11:10 am

Posted by broll on 2013-06-15 08:42:22