lxx. Fitch Cheney Five-Card Trick

Problem (W. Fitch Cheney, 1950). A spectator picks 5 cards from a standard 52-card deck and hands them to the assistant, who hides one and shows the other 4 in an order of their choosing. The magician names the hidden card. How?

Answer. Among 5 cards two share a suit (pigeonhole: 4 suits). On a 13-hour clock of ranks, one of those two is at most 6 steps clockwise from the other. Hide that one; show the other first (it gives the suit and the base rank); order the remaining 3 cards to encode the distance $\mathrm{1..6}$ ($3!=6$ orders).

Fact	Value
distance encoding, cards compared by (rank, suit) as low / mid / high	1 = LMH, 2 = LHM, 3 = MLH, 4 = MHL, 5 = HLM, 6 = HML
largest deck for which a 5-card trick exists	$5!+5-1=124$ (Kleitman and Kwiatkowski, 1976)
general: $n$ cards chosen, $n-1$ shown in order	deck of up to $n!+n-1$ cards, and no more
explicit strategy for the largest deck	hide the card $c_s$ with $s=(\sum c_i)\mathrm{mod}n$ ($c_0<\cdots <c_{n-1}$); the order of the shown cards encodes the hidden card’s position among the unseen cards

// Classic trick. Card c in 0..51: suit c / 13, rank c % 13. Returns the 4 cards to show, in order.
vector<int> cheneyEncode(vector<int> hand) {
    sort(all(hand));
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if (i != j && hand[i] / 13 == hand[j] / 13) {
        int d = ((hand[j] - hand[i]) % 13 + 13) % 13;   // hide hand[j], d steps after hand[i]
        if (d < 1 || d > 6) continue;
        vector<int> rest; for (int k = 0; k < 5; k++) if (k != i && k != j) rest.push_back(hand[k]);
        static const int ord[6][3] = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
        vector<int> shown = {hand[i]};
        for (int t = 0; t < 3; t++) shown.push_back(rest[ord[d - 1][t]]);   // rest is sorted: L, M, H
        return shown;
    }
    return {};                                           // impossible: two cards always share a suit
}
int cheneyDecode(const vector<int>& shown) {
    vector<int> rest(shown.begin() + 1, shown.end()), s = rest; sort(all(s));
    int code = 0;                                        // rank of the permutation, 0..5
    static const int ord[6][3] = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
    for (int p = 0; p < 6; p++) if (rest[0] == s[ord[p][0]] && rest[1] == s[ord[p][1]]) code = p;
    int suit = shown[0] / 13, rank = (shown[0] % 13 + code + 1) % 13;
    return suit * 13 + rank;
}
 
// General trick: deck 0..N-1 with N <= n! + n - 1; hand of n cards; show n - 1 of them in an order.
vector<int> generalEncode(vector<int> hand) {
    int n = sz(hand); sort(all(hand));
    ll sum = 0; for (int c : hand) sum += c;
    int s = int(sum % n), h = hand[s];
    vector<int> shown; for (int i = 0; i < n; i++) if (i != s) shown.push_back(hand[i]);
    ll T = sum - h, r = ((-T) % n + n) % n, q = (h - s - r) / n;   // h - s = q n + r: position among unseen cards
    vector<int> pool = shown, res;                       // write q in the factorial number system
    for (int k = n - 1; k >= 1; k--) {
        ll f = 1; for (int t = 1; t < k; t++) f *= t;
        int idx = int(q / f); q %= f;
        res.push_back(pool[idx]); pool.erase(pool.begin() + idx);
    }
    return res;
}
int generalDecode(const vector<int>& shown) {
    int n = sz(shown) + 1; vector<int> pool = shown; sort(all(pool));
    ll q = 0, T = 0;
    for (int k = 0; k < n - 1; k++) {
        int idx = int(lower_bound(all(pool), shown[k]) - pool.begin());
        ll f = 1; for (int t = 1; t < n - 1 - k; t++) f *= t;
        q += idx * f; pool.erase(pool.begin() + idx); T += shown[k];
    }
    ll pos = q * n + ((-T) % n + n) % n;                 // index among cards not shown
    vector<int> s = shown; sort(all(s));
    int c = int(pos);
    for (int x : s) if (x <= c) c++;                     // skip the shown cards
    return c;
}

Proof: the classic trick works

Five cards in four suits: two share a suit (pigeonhole). Their ranks $a\ne b$ on the 13-cycle satisfy $(b-a)\mathrm{mod}13+(a-b)\mathrm{mod}13=13$, so one of the two distances is in $\mathrm{1..6}$; the encoder hides the card that lies $d\le 6$ steps after the other. The first shown card fixes the suit and the start rank, the three others are distinct and totally ordered by card index, so their order is one of 6 permutations, decoding $d$. The hidden card is (same suit, start rank $+d\mathrm{mod}13$). Verified on all $\left(\genfrac{}{}{0ex}{}{52}{5}\right)=2598960$ hands.

Proof: n! + n - 1 is the largest deck, and the sum strategy achieves it

Upper bound. The assistant’s strategy is an injective map from hands ($n$-subsets) to sequences of $n-1$ distinct cards (the magician must recover the hand from the sequence). So $\left(\genfrac{}{}{0ex}{}{N}{n}\right)\le N(N-1)\cdots (N-n+2)$; dividing, $\frac{N-n+1}{n!}\le 1$, i.e. $N\le n!+n-1$.

Construction. Let $c_0<\cdots <c_{n-1}$ and $s=\sum c_i\mathrm{mod}n$; hide $h=c_s$. Exactly $s$ shown cards are smaller than $h$, so among the $N-n+1$ cards the magician cannot see, $h$ has index $p=h-s$. With $T$ the sum of the shown cards, $T+h\equiv s(\mathrm{mod}n)$, so $p\equiv -T(\mathrm{mod}n)$: the magician knows $p\mathrm{mod}n$, and only $q=\lfloor p/n\rfloor$ must be sent. Since $p\le N-n\le n!-1$, $q\le (n-1)!-1$, which fits in the $(n-1)!$ orders of the shown cards (factorial number system). Decoding reverses each step. Verified exhaustively for $n=3$ ($N=8$) and $n=4$ ($N=27$), and on $2\cdot 10^5$ random hands for $n=5$ ($N=124$).

Related notes

• Counting Fundamentals (permutation ranking)
• Socks and Pigeonhole Puzzles
• Poisoned Wine (another information-encoding puzzle)