Five Pat Hands

Ashowman deals twenty-five cards face down and offers a wager. He claims he can gather the cards into five poker hands so good that no player would draw to improve any of them: five pat hands, side by side. The mark knows his poker. A pat hand is rare, and five of them out of twenty-five cards dealt at random sounds like a swindle in the showman’s favour. He takes the bet. The showman turns the cards up, sorts them into five piles, and collects. The trick has a name, Maverick Solitaire, after the television western that made it briefly famous, and behind the patter is a fact about counting.

Why the showman wins

A pat hand in draw poker is one a player would keep rather than draw to: a straight, a flush, a full house, four of a kind, a straight flush, or a royal flush. Each is uncommon on its own. The odds against being dealt one in five cards run from about $254$ to $1$ for a straight up to $649\,739$ to $1$ for a royal flush. Five of them at once, from cards the mark himself shuffled, feels impossible.

The feeling is wrong, and the reason is the number of ways the cards can be split. Twenty-five distinct cards divide into five unordered hands of five in $$\frac{1}{5!}\prod_{i=1}^{5}\binom{5i}{5} \;=\; \frac{25!}{(5!)^{5}\,5!} \;=\; 5\,194\,672\,859\,376$$ ways, a little over five trillion. With that many arrangements to try, a hand assignment that makes all five piles pat almost always exists somewhere among them. An old estimate from the rec.puzzles newsgroup puts the chance of success above $98\%$. The showman is not certain to win, but he is a heavy favourite, and on the rare deals where no arrangement works he can simply decline to bet.

Those rare deals are real, and one can build them deliberately. Suppose the twenty-five cards include the king of clubs but no other king, no queen at all, no value held four times, and at most three clubs besides the king. Then the king of clubs has nowhere to go. It cannot sit in a full house, which would need a second king to pair it or three of another value it could join, nor as the spare card beside four of a kind, since no value appears four times. It cannot complete a flush or a straight flush, since its suit musters only four cards. And it cannot belong to a straight, because every straight through a king needs a queen, and there is none. The king is homeless, and the bet cannot be won. Engineering an impossible deal is easy; recognising whether a given deal is winnable is the part that earns a model.

The model

Number the dealt cards $i = 1, \ldots, 25$ and the hands $k = 1, \ldots, 5$. Each card carries a known value $v_i$, from two up to the ace counted high at fourteen, and a known suit $s_i$. The one family of decisions is where each card goes: $$a_{ik} = \begin{cases} 1 & \text{card } i \text{ is placed in hand } k,\\ 0 & \text{otherwise.} \end{cases}$$

Two linear constraints make the five hands a partition of the deal. Every card lands in exactly one hand, $$\sum_{k} a_{ik} = 1 \qquad \forall i,$$ and every hand receives exactly five cards, $$\sum_{i} a_{ik} = 5 \qquad \forall k.$$

Everything else is the test for “pat,” applied to each hand. It reads most cleanly through two tallies derived from the assignment: the number of cards of each value in a hand, $c_{km} = \sum_{i \,:\, v_i = m} a_{ik}$, and the number of each suit, $d_{kn} = \sum_{i \,:\, s_i = n} a_{ik}$.

Three tests cover six hands

The six pat hands need only three tests, because the rarest three are special cases of the commoner ones.

A flush is five cards of one suit: $d_{kn} = 5$ for some suit $n$. A straight flush and a royal flush are flushes too, so this single test catches all three of them.

A full house or four of a kind is a hand of exactly two distinct values. Five cards drawn from a single deck hold at most four of any value, so two distinct values can split only as four-and-one (four of a kind) or three-and-two (a full house); no other division of five into two parts fits. The test is therefore just that the count of values present, the number of $m$ with $c_{km} \ge 1$, equals two.

A straight is five cards of consecutive value. There are ten such runs, from ace-low $A\,2\,3\,4\,5$ through to ace-high $10\,J\,Q\,K\,A$, and a hand is a straight exactly when the values it holds are one of these ten sets. Since a hand has five cards, holding all five values of a run leaves room for nothing else, so “contains every value of the run” is the whole test.

A hand is pat when it passes at least one of the three tests, and the showman wins when all five hands do at once. There is no quantity to maximise: the model is a pure feasibility question, and a single feasible assignment settles the bet.

A solver

The constraint solver expresses each test as a Boolean that is true exactly when its linear condition holds, then asks that every hand satisfy some test.

from ortools.sat.python import cp_model

# dealt cards; values 2..10, J=11, Q=12, K=13, A=14
DEAL = ([(v, "C") for v in (2, 3, 7, 8, 9, 10, 12, 13)]
        + [(v, "D") for v in (2, 4, 5, 8, 10)]
        + [(v, "H") for v in (3, 4, 6, 11)]
        + [(v, "S") for v in (3, 4, 6, 8, 10, 11, 12, 13)])

# the ten straights, as the value-sets they hold
RUNS = [{2, 3, 4, 5, 14}]
RUNS += [set(range(h - 4, h + 1)) for h in range(6, 15)]


def solve(deal=DEAL):
    m = cp_model.CpModel()
    n = len(deal)
    vals = sorted({v for v, _ in deal})
    suits = sorted({s for _, s in deal})
    a = {(i, k): m.NewBoolVar("") for i in range(n) for k in range(5)}
    for i in range(n):
        m.Add(sum(a[i, k] for k in range(5)) == 1)  # card in one hand
    for k in range(5):
        m.Add(sum(a[i, k] for i in range(n)) == 5)  # five cards per hand
    for k in range(5):
        present = {}
        for v in vals:
            cnt = sum(a[i, k] for i in range(n) if deal[i][0] == v)
            b = m.NewBoolVar("")
            m.Add(cnt >= 1).OnlyEnforceIf(b)
            m.Add(cnt == 0).OnlyEnforceIf(b.Not())
            present[v] = b
        two = m.NewBoolVar("")  # full house or four of a kind
        m.Add(sum(present.values()) == 2).OnlyEnforceIf(two)
        m.Add(sum(present.values()) != 2).OnlyEnforceIf(two.Not())
        tests = [two]
        for s in suits:  # a flush in suit s
            cnt = sum(a[i, k] for i in range(n) if deal[i][1] == s)
            b = m.NewBoolVar("")
            m.Add(cnt == 5).OnlyEnforceIf(b)
            m.Add(cnt != 5).OnlyEnforceIf(b.Not())
            tests.append(b)
        for run in RUNS:  # a straight
            lits = [present[v] for v in run if v in present]
            b = m.NewBoolVar("")
            if len(lits) == 5:
                m.AddBoolAnd(lits).OnlyEnforceIf(b)
                m.AddBoolOr([x.Not() for x in lits]).OnlyEnforceIf(b.Not())
            else:
                m.Add(b == 0)
            tests.append(b)
        m.AddBoolOr(tests)  # hand k must be pat
    cp = cp_model.CpSolver()
    cp.Solve(m)
    return [[deal[i] for i in range(n) if cp.Value(a[i, k])]
            for k in range(5)]

The elusive deal

The deal in Figure 36.1 is the one Chlond singles out, twenty-five cards that hold a solution but hide it well: eight clubs, five diamonds, four hearts and eight spades, with no aces and no obvious run. By eye it resists. The model returns a partition at once. Two of the hands are flushes, one in spades and one in clubs; two are straights, one running nine to king and one running two to six; and the last is a full house, three eights over a pair of fours. Every dealt card is spent, and each pile is pat.

This is the showman’s edge made exact. He does not need to see the arrangement in advance, only to trust that one almost always exists, and the trillions of possible splits make that trust sound. Where his confidence fails, on a deal salted to strand a lonely king, the same model reports infeasibility rather than a split, and the honest showman keeps his money in his pocket.

Sources. The five-pat-hands proposition is best known as “Maverick Solitaire,” from the Maverick episode “Rope of Cards” (first broadcast $19$ January $1958$), in which Bret Maverick wins it as a courtroom wager; the bet recurs in the Alias Smith and Jones episode “The McCreedy Bust” ($1971$). The counting argument, the twenty-five-card configuration of Figure 36.1, and the integer-programming treatment follow Martin J. Chlond, Five Pat Hands, INFORMS Transactions on Education volume $12$, number $3$ ($2012$), pages $164$–$165$; the formulation here groups the six pat hands into the three tests Chlond uses, but classifies each hand by its value and suit counts rather than by his ordered-position model. The single-deck odds against the individual pat hands are the standard figures tabulated by John Scarne, Scarne’s Complete Guide to Gambling (Simon and Schuster, New York, $1961$): the $2\,598\,960$ five-card hands include $10\,200$ straights, $5\,108$ flushes, $3\,744$ full houses, $624$ fours of a kind, $36$ straight flushes and $4$ royal flushes, giving the quoted odds against to the nearest figure. The arrangement count $5\,194\,672\,859\,376$, the displayed split, and the impossibility of the lonely-king deal are all reproduced by the models accompanying this chapter.