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.
(In reply to
Possible solution by broll)
This might be a good start, Broll, but I am not completely sure. There are two problems that I notice need to be addressed.
1) You put D in the A group, but haven't proved that D knows C (who is already in the group). This is just a little gap, which I am pleased to fill in. Neither C nor D know B, so C and D must know each other, because we cannot have 3 people who are mutual strangers.
2) You didn't say so explicitly, but the kth person to be placed should be selected to be somebody who doesn't know somebody that has been placed already. He will know everybody else that has been placed, otherwise there are k people and k introductions required between them.
2)More seriously, what if we can't find a kth person that doesn't know one of the (k-1) that are already in groups? Let's say that everybody else in the whole town knows the first k-1 people. If they all know each other, then we are all set. Put them all into one group or the other. But if they do not all know each other, then I think that we need to start two new groups, which we will later add into A and B respectively.
Are there any more problems lurking? I don't think so, but I don't have time to examine it now.
re: Possible solution
