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
re: Solution by Dan Rosen)
The straight forward solution is the following :
Each person is represented by a point in the plane. All the points are connected by straight lines signifying acquaintance. Strangers are marked by broken lines. At first are all junctions (persons) marked as belonging to group A. When encountering a broken line, one end of it is changed to the other group , thus avoiding a broken line ( unfamilier) within the group. Solid lines may of course have different endings. The property that any chosen group of m people (polygonial trajectory) contains no more than (m-1) broken lines, ensures that there develop no conflicts arising by going along a closed trajectory starting with A and ending up at the same point needing to mark it as B. This would happen for example by moving along a triangle of 3 broken lines. As only 2 broken lines are allowed in a triangle, this is avoided.
So , if no broken line gets different marks at its ends there will have been constructed 2 all familiar groups .
re(2): Solution
