A problem proposed by Ashay Burungale of Satara, Maharashtra, India, in the November 2008 issue of American Mathematical Monthly: In a certain town of population 2n + 1, all relations are reciprocal: If Person 1 knows Person 2, then Person 2 knows Person 1. For any set A that consists of n citizens, there’s some person among the remaining n + 1 who knows everyone in A. Prove that there’s some citizen of the town who knows all the others.
|
SelectClick for Answer |
Kenneth Schilling of the University of Michigan offered this solution: Call any set of citizens all of whom know one another a clique. Now if there’s a clique B that has fewer than n + 1 citizens, then by hypothesis some citizen who’s not in B knows everyone in B, and we can add that person to B to form a larger clique. That means that a clique exists of size n + 1. The set A of citizens who aren’t in B has size n. So by hypothesis there’s some person in B who knows every person in A, and hence that person knows everyone in the town.
(Ashay Burungale and Kenneth Schilling, “Getting to Know You, Directly and Indirectly,” American Mathematical Monthly 115:9 [November 2008], 862.)
|
