A Clique of Acquaintances

I thank Professor W. McWorter for bringing this problem to my attention. The problem has been posted to one of the wu:forums.

There are 2n + 1 people with the property that, for any n of them, there is some one of the 2n + 1, not among the n, acquainted with all n. Show that there is a person that is acquainted with every one present.

(The problem makes a tacit assumption that "being acquainted" is a symmetric relationship.)

Solution

Solution

The problem has been characterized as a quickie: once you hit on the right idea, the solution takes just a few lines.

The problem has a natural representation as a graph: two nodes are connected by an edge iff the fellows they represent are acquainted. The nice idea that makes the problem a quickie is that, under the conditions of the problem, there is always a clique of size at least n + 1. A clique is a term for a subgraph that, as a graph, is complete.

Let's first show that the existence of a clique C of size n + 1 leads to a solution of the problem. Let R be the remaining nodes. By the conditions of the problem, there exists a node outside R that is connected to every node in R. Since this node belongs to C (in which all the nodes are connected to each other), this node is connected to all other nodes.

Now, let's form a clique of size n + 1. Pick any n nodes. There is a node that is connected to each of the selected ones. This one, along with any of the selected, form a clique of size 2. Arbitrarily add n - 2 nodes to these two. There is a node that is connected to each of the selected ones. Along with a 2-clique it forms a 3-clique. We may continue in this manner until we get an n-clique. For this, as for any collection of n nodes, there is a node connected to each of the selected ones. Together they form an (n + 1)-clique.

A short while after posting this page I found that the problem was proposed in 2006 at the American Math Monthly by Ashay Burungale from India, with two solution published in 2008 (v. 115, n. 9, p. 862). The first solution by Kenneth Schilling is a paraphrase of the above. Another (by Christopher Carl Heckman) is essentially different.

We prove the contrapositive: If nobody knows everyone, then some set A of n citizens is not completely known by anyone outside A. We first color each citizen red or green as follows. If p is not yet colored, choose some p' unknown to p. If p' is already colored, give p the opposite color. Otherwise, give p and p' opposite colors. At the end, everyone has a color opposite from that of someone he or she does not know. The less-frequent color occurs at most n times; let A be a set of size n including all those with that color. Each person outside A has the other color and hence does not know everyone in A.

The two solutions were followed by

Editorial comment. The problem of course is a statement about graphs (perhaps the popularity of the problem stemmed from not using that language). In the language of graph theory, it states that a graph of odd order has a vertex adjacent to all others if each set with fewer than half the vertices has a common neighbor. Several solvers did use graph theoretic language and arguments.

71534772