The Card Trick

Aperformer hands a packet of cards to the audience and turns away. Three spectators cut the packet in turn, each lifting some cards from the top and dropping them underneath, then the three of them take the top three cards, one each. The performer, still without looking, asks only two things: which of the three holds the lowest card and which the highest, and which of the three cards are red. From those scraps, an ordering and a few colours, the performer names all three cards exactly. It looks like mind-reading. It is a cyclic sequence of exquisite design, and the sequence can be built by an integer program.

The trick

The deck is special. Take a standard pack, remove the four kings to leave forty-eight cards, and lay them in a particular cyclic order, fixed once and memorised. Cutting a cyclic sequence does not disturb it: lifting cards from the top and dropping them below only rotates the cycle, so after any number of cuts the three cards on top are still three that sit consecutively in the fixed order. The spectators, cutting freely, only choose where in the cycle the performer will read, never the order itself.

So the performer must recover three consecutive cards of the cycle from a thin description of them: their three colours, and which is lowest, middle and highest in rank with the ace counted low. The description is coarse. There are only $2^3 = 8$ possible colour patterns for three cards and only $3! = 6$ possible rank orders, so a window of three cards yields one of just $8 \times 6 = 48$ signatures. The deck has forty-eight cards and so forty-eight windows. If the order is built so that every window wears a different signature, the coarse description is enough: it names the window, the window names its position, and the position names the cards.

The whole trick reduces to one demand on the cyclic order. Every three consecutive cards must have a signature that no other three consecutive cards share. The art is in meeting it.

Two universal cycles

Pull the signature into its two halves, colour and rank, and each half is a small marvel of its own.

A de Bruijn cycle carries the colours. Write each card’s colour as a bit, $0$ for red and $1$ for black, and the colour pattern of a window is a string of three bits. There are eight such strings, and a binary cycle in which every window of three is a different string, all eight appearing, is a de Bruijn cycle of order three. It has length exactly eight, one window per pattern. The cycle $0\,0\,0\,1\,0\,1\,1\,1$ is one: read three at a time around it, wrapping at the end, and the eight triples $000, 001, 010, \ldots$ each show up once. The left ring of Figure 34.1 draws it, red beads for $0$ and black for $1$.

A relative-order cycle carries the ranks. Here only the order within a window matters, not the values, so we want a cycle of numbers in which every window of three has a different low-middle-high pattern, all six appearing. Length six suffices, and $3\,4\,2\,1\,4\,2$ is such a cycle: its windows run medium-high-low, then high-medium-low, and so on through all six orders. The right ring of Figure 34.1 draws it.

Each cycle as an integer program

Both cycles are short enough to find by hand, but each is a clean integer program, and seeing them as one is the point of the chapter. Take the de Bruijn cycle first. Let $b_0, \ldots, b_{7}$ be the bits of a cycle of length eight. The window opening at position $i$ reads the three bits $b_i, b_{i+1}, b_{i+2}$, indices wrapping round, and we name it by the number those bits spell, between $0$ and $7$. The single demand is that the eight window-numbers are all different, which an all-different constraint states directly. Fixing the first window to all zeros pins down one cycle among its rotations.

from ortools.sat.python import cp_model

def debruijn(k):
    L = 2 ** k
    m = cp_model.CpModel()
    b = [m.NewBoolVar("") for _ in range(L)]
    window = []
    for i in range(L):
        v = m.NewIntVar(0, L - 1, "")          # the k bits as a number
        m.Add(v == sum(b[(i + j) % L] * 2 ** (k - 1 - j) for j in range(k)))
        window.append(v)
    m.AddAllDifferent(window)                  # every window distinct
    for j in range(k):
        m.Add(b[j] == 0)                   # open at the all-zeros window
    s = cp_model.CpSolver()
    s.Solve(m)
    return [s.Value(x) for x in b]

The rank cycle is the same idea with a subtler signature. The numbers in a window have no fixed values, only an order, so we read each window not as a number but as a pattern of three comparisons: is the first below the second, the second below the third, the first below the third. Those three yes-or-no answers name the order, and again we ask that the six windows all answer differently.

def order_cycle():
    L = 6
    m = cp_model.CpModel()
    a = [m.NewIntVar(1, 6, "") for _ in range(L)]
    code = []
    for i in range(L):
        p, q, r = a[i], a[(i + 1) % L], a[(i + 2) % L]
        m.Add(p != q); m.Add(q != r); m.Add(p != r)
        lt = [m.NewBoolVar("") for _ in range(3)]
        for t, (u, w) in enumerate([(p, q), (q, r), (p, r)]):
            m.Add(u < w).OnlyEnforceIf(lt[t])
            m.Add(u > w).OnlyEnforceIf(lt[t].Not())
        c = m.NewIntVar(0, 7, "")
        m.Add(c == 4 * lt[0] + 2 * lt[1] + lt[2])   # the order as a code
        code.append(c)
    m.AddAllDifferent(code)                      # all six orders distinct
    s = cp_model.CpSolver()
    s.Solve(m)
    return [s.Value(x) for x in a]

Each program returns a cycle with the property its windows are made to have, and that property is the whole of what the trick needs from it.

The product, and the trick

The deck must carry both signatures at once, so its order is a product of the two cycles: a single sequence of forty-eight cards whose colour pattern runs through a colour cycle and whose ranks run through a rank cycle, arranged so that the combined signature of every window is unique. Eight colour patterns and six rank orders make forty-eight pairs, the deck has forty-eight windows, and a good product spends each pair on exactly one window. There is no tidy formula for the product, and finding a card order that realises it took its inventors an unhurried search and its modeller a few helping constraints, but the property, once a product is in hand, is exact and checkable: across all forty-eight windows, no signature repeats. That is the fact the performer trusts. Three cards come up; their colours and order spell a signature; the signature occurs in just one place in the memorised cycle; and the three cards that sit there, in their known order, are named.

What the puzzle teaches

The trick is a lesson in how little information can suffice when the world it describes is built to be read. A coarse description, three colours and an order, would be hopeless against a shuffled deck of a hundred thousand triples, but against a deck arranged as a product of universal cycles it is exact, because the arrangement has spent its every degree of freedom making windows distinguishable. For the integer programmer the recurring move is the constraint over sliding windows: lay an all-different across every window of a cyclic sequence, and what drops out is a universal cycle, the shortest possible object in which every local pattern of a kind appears exactly once. De Bruijn cycles route shift registers and assemble genomes from short reads; relative-order cycles underlie a small genre of card magic. Both are the same constraint wearing different clothes, and both are two lines of a model away.

Sources. The card trick and its mathematics of products of universal cycles are due to Persi Diaconis and Ronald Graham, “Products of Universal Cycles,” in A Lifetime of Puzzles, edited by Erik D. Demaine, Martin L. Demaine and Tom Rodgers (A. K. Peters, Wellesley, $2008$), pages $35$–$55$. The integer-programming formulations of the de Bruijn cycle and the relative-order cycle, and the model that searches for a card order realising the product, follow Martin J. Chlond, Puzzle—A Magical IP, INFORMS Transactions on Education volume $9$, number $3$ ($2009$), pages $188$–$189$; the reduced forty-eight-card deck and the example product are his. The de Bruijn cycle of order three drawn here and the relative-order cycle $3\,4\,2\,1\,4\,2$ are reproduced by the models above, which are checked to have the distinct-window property; the product’s forty-eight distinct signatures are confirmed directly. De Bruijn sequences are named for Nicolaas Govert de Bruijn, who counted them in $1946$.