9.18

From each vertex B to each vertex C there is either a one-step path (a single edge) or a unique two-step path. But we'll analyze the problem by looking at three-step paths as well. Fix two vertices B and C. Suppose there are k different vertices H such that (H,C) is an edge. Call these vertices the "predecessors" of C. Suppose also that there are m different vertices G such that (B,G) is an edge; call these vertices the "followers" of B. How many paths, of length either two or three (but not one) are there from B to C? First answer: there are m such paths. Each two- or three-step path from B to C consists of an edge from B to some vertex G, followed by the unique one- or two-step path from that vertex G to the destination C. Since there are m edges leading out of B, and each can be completed to exactly one path of length 2 or 3 to C, there are m such paths. Second answer: k. Each two- or three-step path from B to C is a one- or two-step path from B to one of C's predecessors H, followed by a one-step path from that vertex to C. Each of the k predecessors of J accounts for exactly one such path. So we must have k=m. By the same reasoning, each vertex D has exactly k two- or three-step paths to C, and so has exactly k successors. Similarly we can see that each vertex has exactly k predecessors. (In graph terminology, each vertex has in-degree k and out-degree k.) Now consider one- or two-step paths starting at B. There are exactly k vertices H reachable by a one-step path. Since each of these vertices also has exactly k followers, there are exactly (k*k) vertices reachable from B via two-step paths. This accounts for all the vertices, so the total number of vertices is k+(k*k). We know there are thirty to forty vertices, so we must have k=5 and the number of vertices is thirty. It turns out (though this is harder to prove) that the vertices can be given consistent labels of the form Vij, where i and j are two different indices from the set {1,2,...,k+1}, and where an edge goes from Vij to Vkh if and only if j=k. Illustrating in a smaller case k=2, we would have 6=2+4 vertices V12, V13, V21, V23, V31, V32, and twelve edges (two coming out of each vertex): (V12,V21), (V12,V23), (V13,V31), (V13,V32), (V21,V12), (V21,V13), (V23,V31), (V23,V32), (V31,V12), (V31,V13), (V32,V21), (V32,V23).

9.9

Q:
In every round robin tennis tournament, there is a player who, for any other player p, has either beaten p or beaten some player who has beaten p.
Zh:
n个人中每两个人之间都进行过一次比赛。假设比赛不可能出现平局。证明，一定能找出这样的一个人，对于其它任何一人p，他击败了p或者击败了某个打败了p的人。

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

There may be several players with the stated property: for any other player p, this one either beat p or beat a player who has beaten p. The nice idea that makes the problem a quickie is that the player who won most of the games has this property. Let P be such a player and GP a group of players beaten by P. Assume there is a player q not in GP who, in addition, has not lost to any p in GP. Since, it's a round robin tournament, that is a tournament in which every player meets any other player, q met with P and any player from GP. Moreover, since he has not lost to either P or any member of the GP group, he won all those meets implying that he won more meets than P. Contradiction with the selection of P. In other words, any q that is not in GP has been beaten by a member of the GP group.

The problem admits a recasting in terms of Graph Theory. Start with a complete graph Kn, n > 1. (A graph is complete if any two nodes are joined by an edge.) Convert Kn to a directed graph (digraph) by arbitrarily assigning to each edge a direction. The problem stipulates the existence of a node from which any other node is accessible by a directed path of the length at most 2.

9.8

Q:
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.
A:
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.