The Magic Trick "In TetraCycles"
A magician holds a deck of SET with eighty-one distinct cards. Each card contains four features that describe the image on the card. They are "shape", "color", "number", and "shading". Four volunteers are chosen from the audience. The magician cut the deck repeatedly and hands out four consecutive cards to the four volunteers. Then the magician allows volunteers to pick a feature that they prefer to describe. Let us assume that the "color" feature is picked. The magician then asked, "Since you picked color, would all of you with a red card please stand up?". After volunteers stand up accordingly, the magician asks "Would all of you with a green card please stand up?" Then the magician can name all four cards accurately, including their shapes, colors, numbers, and shadings.
We will not talk about how to play the game of SET, the following diagram by Quanta Magazine explains the basic rule of the game.
This trick called "In TetraCycles" is a variation on the "In Cycles" trick developed by Persi Diaconis and Ron Graham and was elaborated in the book "Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks". These tricks have various generalizations and magicians may be able to apply them to various decks.
It is surprising that the magician can detect all the cards, especially when no information is given about the other three features. The secret is that the deck is arranged in a very special order, where for every feature, the combination within every four consecutive cards is unique. Such properties are also cyclic, therefore is preserved when cutting the deck. It is astonishing that such a deck arrangement even exists as below:
How is such an arrangement possible? Turns out that the magician is using the properties of a de Bruijn sequence, which contains every possible subsequence. A de Bruijn sequence is a cyclic sequence of a given alphabet
|shapes||colors||number of shapes||shading|
|oval ||red ||one ||solid |
|squiggle ||green ||two ||unfilled |
|diamond ||purple ||three ||striped |
How do we ensure that the trick works no matter which features the audience pick? We need to ensure that each feature is mapped to its own de Bruijn sequence. This is a challenging process since every SET cards are distinct, meaning that if we line up the four de Bruijn sequence and read off each column, each column will be representing a SET card and the column cannot repeat itself. There are in total over
Now we will generate a de Bruijn sequence with a graphical approach. A de Bruijn graph is a directed graph. We will layout the main procedures as follows:
- Generate all vertices of the de Bruijn graph based on input values of
- Find all possible edges between these vertices.
- Find one random Eulerian circuit.
- Find the corresponding de Bruijn sequence based on the Eulerian circuit.
By following this process, we have generated a de Bruijn sequence:
Thus we have
Now by assigning
The cheat sheet below is designed for the shape feature, where 'D' stands for diamond, 'S' stands for squiggle, and 'O' stands for Oval. Once volunteers answer both questions regarding shape, we will be able to determine each card's shape. Then we refer to the cheat sheet to find the corresponding column. The exact four cards are shown on the right.