TAOCP 2.3.4.2 Exercise 16

Section 2.3.4.2: Oriented Trees

Exercise 16. [**] $$M24$$ In a popular solitaire game called "clock," the 52 cards of an ordinary deck of playing cards are dealt face down into 13 piles of four each; 12 piles are arranged in a circle like the 12 hours of a clock and the thirteenth pile goes in the center. The solitaire game now proceeds by turning up the top card of the center pile, and then if its face value is $k$, by placing it next to the $k$th pile. (The numbers $1,2,\ldots,13$ are equivalent to A, 2, ..., 10, J, Q, K.) Play continues by turning up the top card of the $k$th pile and putting it next to its pile, etc., until we reach a point where we cannot continue since there are no more cards to turn up on the designated pile. (The player has no choice in the game, since the rules completely specify what to do.) The game is won if all cards are face up when play terminates. [Reference: E. D. Cheney, Patience (Boston: Lee & Shepard, 1870), 62-65; the game was called "Travellers' Patience" in

England, according to M. Whitmore Jones, Games of Patience (London: L. Upcott Gill, 1900), Chapter 7.]

Show that the game will be won if and only if the following directed graph is an oriented tree: The vertices are $V_1,V_2,\ldots,V_{13}$; the arcs are $e_1,e_2,\ldots,e_{12}$, where $e_j$ goes from $V_j$ to $V_k$ if $k$ is the bottom card in pile $j$ after the deal.

(In particular, if the bottom card of pile $j$ is a "$j$," for $j\ne13$, it is easy to see that the game is certainly lost, since this card could never be turned up. The result proved in this exercise gives a much faster way to play the game!)

Verified: no
Solve time: 5m16s

Let $G$ be the directed graph with vertices $V_1,\dots,V_{13}$, where $V_{13}$ is the center pile, and where for $j\neq 13$ there is an arc

$$ e_j:V_j\to V_{b(j)}, $$

$b(j)$ being the value of the bottom card of pile $j$.

Since there are $12$ arcs and $13$ vertices, every vertex except $V_{13}$ has outdegree $1$, and $V_{13}$ has outdegree $0$.

We shall prove that the game is won if and only if $G$ is an oriented tree rooted at $V_{13}$.

1. A basic counting lemma

For each $j$, let $N_j$ be the number of times pile $j$ is visited, where a visit means that a card is turned up from that pile.

Every visit to pile $j$ is caused by exposing a card of value $j$, except for the initial visit to the center pile $V_{13}$.

Since there are exactly four cards of each value $j$,

$$ N_j\le 4 \qquad (j\neq 13), $$

and for $j=13$,

$$ N_{13}\le 1+3=4, $$

because one visit is initial and only three further kings remain in the deck.

Hence

$$ N_j\le 4 \qquad (1\le j\le 13). $$

The game is won exactly when all $52$ cards are exposed. Since each visit exposes exactly one card, this is equivalent to

$$ \sum_{j=1}^{13}N_j=52. $$

Because there are $13$ piles and each $N_j\le4$, the sum can equal $52$ only if

$$ N_j=4\qquad(1\le j\le13). $$

Thus:

The game is won if and only if every pile is visited exactly four times.

We shall use this repeatedly.

2. A key invariant

For a vertex $V_j$, let

$$ P(j) $$

denote the statement that pile $j$ is visited four times.

We claim that for $j\neq13$,

$$ P(j)\iff P(b(j)). $$

Indeed, consider pile $j$.

The fourth visit to pile $j$ exposes its bottom card. That card has value $b(j)$. Therefore the fourth visit to $j$ produces one visit to pile $b(j)$.

Conversely, among the four cards of value $b(j)$, exactly one is the bottom card of pile $j$. Hence one of the visits to pile $b(j)$ occurs if and only if the bottom card of pile $j$ is exposed, and that happens if and only if pile $j$ receives its fourth visit.

Since pile $b(j)$ can receive at most four visits altogether, we obtain

$$ N_{b(j)}=4 $$

if and only if the visit arising from the bottom card of pile $j$ occurs, which is equivalent to

$$ N_j=4. $$

Thus

$$ P(j)\iff P(b(j)). $$

In graph language:

Along every arc $V_j\to V_{b(j)}$, the property “visited four times” is transmitted in both directions.

Therefore, if two vertices lie in the same weakly connected component of $G$, then either both satisfy $P$ or neither does.

3. If the game is won, then $G$ is an oriented tree

Assume the game is won.

Then every pile is visited four times, so $P(j)$ holds for every vertex.

Suppose $G$ were not an oriented tree rooted at $V_{13}$.

Since every vertex except $V_{13}$ has outdegree $1$, some vertex would fail to have a directed path to $V_{13}$. Following outgoing arcs from such a vertex, one eventually repeats a vertex, producing a directed cycle $C$ not containing $V_{13}$.

Let $W$ be the set of vertices from which the directed path eventually reaches $C$. No vertex of $W$ can reach $V_{13}$.

Because $C$ is a directed cycle and every vertex of $W$ has outdegree $1$, the set $W$ is a union of connected components of the underlying undirected graph. In particular, $V_{13}\notin W$.

By the equivalence proved above, the truth value of $P$ is constant on each connected component. Since $P(V_{13})$ is true, every vertex in the component containing $V_{13}$ satisfies $P$. Therefore every vertex in $W$ must satisfy the opposite value of $P$, namely false.

Hence no vertex of $W$ is visited four times.

But $C\subseteq W$, so the vertices of $C$ are not visited four times. Therefore not all piles are visited four times, contradicting the fact that the game was won.

This contradiction shows that $G$ must be an oriented tree rooted at $V_{13}$.

4. If $G$ is an oriented tree, then the game is won

Assume now that $G$ is an oriented tree rooted at $V_{13}$.

The underlying undirected graph is connected. Since $P(j)\iff P(b(j))$ along every arc, the truth value of $P$ is constant throughout the whole tree.

Therefore either

$$ P(j)\text{ is true for all }j, $$

$$ P(j)\text{ is false for all }j. $$

We now determine which alternative occurs.

The center pile $V_{13}$ is visited once at the start. During play there are only three other kings in the deck. Thus $V_{13}$ can receive at most three additional visits.

Consequently,

$$ N_{13}=4 $$

if and only if every king in the deck is eventually exposed.

Suppose $N_{13}<4$. Then $P(13)$ is false. Since $P$ is constant on the connected tree, $P(j)$ is false for every vertex $j$.

Hence no pile is visited four times.

But the game begins by visiting $V_{13}$, and whenever a card of value $j$ is exposed, pile $j$ receives a visit. Since $52$ cards are present and every visit exposes one card, the game cannot terminate before some pile receives its fourth visit. Therefore at least one pile must be visited four times, a contradiction.

Thus $P(13)$ is true.

Since $P$ is constant on the connected tree, $P(j)$ is true for every vertex $j$. Therefore

$$ N_j=4\qquad(1\le j\le13). $$

Every pile is visited four times, so all $52$ cards are exposed.

Hence the game is won.

5. Conclusion

We have shown:

If the game is won, every pile is visited four times.
For every arc $V_j\to V_{b(j)}$, the condition “visited four times” holds at $V_j$ if and only if it holds at $V_{b(j)}$.
Therefore the set of vertices visited four times is a union of connected components of the bottom-card graph.
If the graph is an oriented tree, it is connected, so either all vertices are visited four times or none are.
Since the center pile is visited four times, all vertices are visited four times, and the game is won.
Conversely, if the game is won, all vertices are visited four times; hence the graph cannot contain a directed cycle disjoint from $V_{13}$, so every vertex reaches $V_{13}$, and the graph is an oriented tree rooted at $V_{13}$.

Therefore the clock game is won if and only if the directed graph determined by the bottom cards is an oriented tree rooted at $V_{13}$. ∎