Solution
The Largest Magic Deck
Show the problem again
A deck contains N distinct cards, labelled 1 to N, with no suits or other features. An audience member picks any five cards. The assistant, who sees them, secretly chooses one to hide, then lays the other four face up in a row from left to right. The magician, who has not seen the five cards, looks at the row and names the hidden card. The assistant and magician agree on a deterministic scheme in advance, and the only information passed is which four cards are shown and in what order (no hidden signals of any other kind). What is the largest N for which such a scheme exists?
Worked solution
The answer is 124. A scheme assigns to each 5-card hand a message, an ordered list of four of its cards, such that the magician can decode the hidden card. Since the message determines the hidden card (and hence the whole hand), two different hands can never share a message. There are C(N,5) hands and N(N−1)(N−2)(N−3) messages, so we need C(N,5) ≤ N(N−1)(N−2)(N−3). Dividing, this is (N−4)/120 ≤ 1, i.e. N ≤ 124. Conversely, for N ≤ 124 consider the bipartite graph joining each hand to the 5 × 24 = 120 messages it can produce. Each hand has degree 120, and each message (an ordered four-tuple) is adjacent to exactly N − 4 ≤ 120 hands. By Hall's theorem such a graph has a matching covering every hand, and a matching is exactly a valid scheme. For N = 124 the counts are tight: the matching uses the messages perfectly. The bound was also checked by computer on smaller analogues (hands of 3 cards with 2 shown: N = 8 works and N = 9 fails; hands of 4 cards with 3 shown: N = 27 works and N = 28 fails), matching the formula (k+1)! + k for k shown cards, which gives 124 for k = 4.
Source: Based on Fitch Cheney's five-card trick (attributed to W. Fitch Cheney Jr.), popularised in recreational mathematics; the deck-size bound is a standard exercise. Statement written for AxiomIQ.