27 Card Trick

Original link:
https://curiosity.com/paths/beautiful-card-trick-numberphile-numberphile

The other day I came across this little card trick that I have since then embraced and have been practising myself. Halfway through the video, the guy attempts to explain how the trick works in an informal way, but then skips the most crucial step of the explanation and instead says that we shouldn't lose too much sleep about it. Well, I did lose my sleep. I couldn't go to bed until I finally grasped the trick. This post explains my way of understanding how the trick works.

The 27 card trick can be seen as a little algorithm, and as such, it takes an input and yields an output:

Input

• 27 cards
• A card $C$ (unknown)
• A number $x \in [0,26]$ (the number we are told minus one)
• A labelling or label function $L$ that assigns a unique label to each card such that $L(C) = y$ ($y$ is also unknown)

Output

• A new labelling function $L'$ such that $L'(C) = x$

Card labels here are simply numbers $[0..26]$. The cards are given to us in some initial order, and the labels are the positions of the cards in that initial sequence. Having just 27 cards, we can encode each label/position with three ternary digits. This is, in fact, where the number 27 comes from ($3^3$).

In our input, we are given a card $C$ (unknown) and a label $L(C) = y$ (also unknown). This label can be encoded with three digits, $D_2D_1D_0$, that is, $y = D_2 \cdot 3^2 + D_1 \cdot 3 + D_0$. Our goal is to transform these three digits, $D_2D_1D_0$, into three new digits $E_2E_1E_0$ that encode the number $x$, that is, $E_2 \cdot 3^2 + E_1 \cdot 3 + E_0 = x$. To do so, we deal the cards in three different stacks three times to transform each of the digits.

When we deal the cards for the first time, we are forming three stacks or groups based on the card labels modulo 3. The first stack contains all cards $c$ such that $L(c) \mod 3 = 0$. The second stack contains those congruent to $1$, and the third stack those congruent to $2$. By asking which stack the card is in, the player is telling us the value of $y \mod 3$, that is, the first digit of $y$, $D_0$. When we pick up the stacks, we reorder the stacks by placing this stack on the top, middle, or bottom to enforce that the new first digit be equal to $E_0$ instead. This yields a new labelling where the labels ending in $D_0$ are swapped with those ending in $E_0$. Repeating this process two more times enforces the value of the other two digits, $E_1$ and $E_2$, yielding a final labelling function $L'$ such that $L'(C) = E_2E_1E_0 = x$.

So in the end, the trick turned out to be nice and simple. Everything is known, and we just need to determine the output from our input. The hardest part is familiarising yourself with base 3 number conversions. That, and remembering to subtract one from the number you are told.