Card Trick

The start of a series of bonus questions and solutions done in the Graph Theory course at EPFL (MATH-360)

XDA Wallpapers

Question from Session 2: Two people perform a card trick. The first performer takes 5 cards from a 52-card deck (previously shuffled by a member of the audience), looks at them, keeps one of the cards and arranges the remaining four in a row from left to right, face up. The second performer guesses correctly the hidden card. Prove that the performers can agree on a system which always makes this possible, and devise one such system.

Definitions
Let us assume that the 52-card deck consists of 4 suits of 13 cards. Let us label the decks C for clubs, S for spades, H for hearts and D for diamonds. A suit X has elements x₁, x₂, x₃, …, ₁₃ that denote the 13 cards in each deck, the subscript being the number value of the card.
Between cards of the same deck, a card with a higher number value has a higher “deck value” (so c₂ is more valuable than c₁). Between cards of different decks, spades are the most valuable, followed by hearts, diamonds, and clubs.

Guessing the suit of the hidden card
When player 1 (P1) draws a set of five cards from the pile, it is impossible to have every card of a different suit, as there are only 4 suits. Given a suit X with at least 2 cards in the drawn pile which are x_n and x_m, it is possible for P1 to choose x_n as hidden card, and then to place x_b as the r-th card in the row (r is predefined and can vary so as to make the trick harder for a spectator to figure out) as a signal to the P2 that the hidden card is of the suit X.
For example, if r=1, X=C, then P1 can choose to make the arrangement

Guessing the number on the hidden card
Next, the number on the revealed card x_m and the identities of the other three cards a,b and c are used to communicate the number n of the hidden card. For this, the performers can make use of a graph consisting of a cycle C of 13 vertices v₁, v₂, v₃,…, v₁₃, one for each number value of the card as follows:

The cards a,b and c are defined by P1 and P2 as their deck value, so that a < b < c. Based on how a,b and c are arranged in the row (ignoring x_m), P2 starts from the point on the graph with the number value m and then moves along the cycle according to the key:

This is because in C, it is possible to reach any vertex from a start point by a maximum of 6 steps (i.e. after covering 6 edges), as demonstrated below:

P1 should pick x_n as the card to hide if it is possible to travel clockwise on C from v_m to v_n within 6 steps.
With these rules, the suit, as well as the number value of x_n, can be unambiguously determined by P2 from the 4 cards displayed by P1.

Overview of performance (Example)
P1 draws 5 cards from the shuffled pile. He draws a set of cards {h₁, c₁₃, s₁, s₃, h₈ }. 2 hearts and 2 clubs are present in the 5 cards on his hand. P1 chooses Hearts as the suit of his hidden card.
As it is possible to travel clockwise on the cycle from v₈ to v₁ within 6 steps, but not possible to travel clockwise on the cycle from v₁ to v₈ within 6 steps, P1 can choose to hide h₁ and display h₈ in the leftmost position in the row:

P2 now knows that the hidden card belongs to the suit H.
To instruct P2 to find out the number value of the hidden card, he fills up the remaining positions of the row with the remaining cards in the order (c, b, a), where a has the lowest deck value and c has the highest deck value. In this case, the sequence (c, b, a),  yields (s₃,s₁,c₁₃). So P1 displays:

By comparing the deck values of the rightmost 3 cards, P2 now understands that he must make six jumps from vertex v₈ on C in the clockwise direction. He does so through a mental calculation and arrives at v₁. He now knows that the hidden card has a number value of 1. With this information in hand, he deduces that the hidden card is h₁, or Ace of Hearts.

□!

(28 Feb 2013, Dorigny in the Switz)