A Magic Trick Using The SET Deck: Zhengyu Li

A Magic Trick Using the SET Deck
Zhengyu Li
Department of Mathematical and Computational Sciences

University of Toronto Mississauga
Canadian Undergraduate Mathematics Conference, August 2020
Li, Zhengyu (UTM) A Magic Trick Using the SET Deck August 2020 1 / 25
Table of Contents
1 Quick Intro of SET
2 Trick Demonstration
3 De Bruijn Sequences and Its Special Properties
4 De Bruijn Graphs
5 A Special De Bruijn Sequence for the SET Deck
6 The “In TetraCycles” Trick Reveal
Table of Contents
4 De Bruijn Graphs
Quick Introduction of SET
The deck consists of 81 unique cards.

They vary in four features across three possibilities for each:

Number: three, two, one
Color: purple, red, green
Filling: striped, solid, unfilled
Shape: Diamond, Oval, Squiggle

Number: three, two, one
Color: purple, red, green
Filling: striped, solid, unfilled
Shape: Diamond, Oval, Squiggle
Table of Contents
4 De Bruijn Graphs
Trick Demonstration
A SET Deck
Table of Contents
4 De Bruijn Graphs
De Bruijn Sequences and Its Special Properties
Definition
A de Bruijn sequence is a cyclic sequence of a given alphabet A with size
k, for which every possible subsequence of length n in A appears as a
sequence of consecutive characters exactly once. We denote a de Bruijn
sequence as B(k, n).
Example
For example, one element of B(3, 3), using alphabet {0, 1, 2}, is
021112120002011001221010222.
You can check that each of the 27 strings of length 3 from the alphabet
{0, 1, 2} appear once and only once as a consecutive subsequence (note
that 220 and 202 start at the end and wrap around).
Table of Contents
4 De Bruijn Graphs
De Bruijn Graphs
One way to build de Bruijn sequences (and thus prove their existence)
comes from graph theory.
Definition
Let A be an alphabet with k elements. The de Bruijn graph G (k, n) is a
directed graph with k n–1 vertices labeled with all possible strings of length
n–1 from A. For each vertex v , labeled a1 a2 . . . an−1 , and each element d
of A, there is a directed edge (labeled d) from v to the vertex labeled
a2 a3 . . . an−1 d. In particular, we have an edge labeled d from vertex v to
vertex w if the label on w can be obtained by appending d to the label on
vertex v with the first character removed.
De Bruijn Graphs of G(3,3)
Definition
An Eulerian circuit or Eulerian cycle is a
trail in a finite graph that visits every
edge exactly once and starts and ends on
the same vertex.
Traversing through an Eulerian circuit
will give us a de Bruijn sequence.
De Bruijn Graphs of G(3,3)
Example
One Eulerian circuit in G (3, 3) is given
by the vertex sequence 22 → 20 → 02 →
21 → 11 → 11 → 12 → 21 → 12 →
20 → 00 → 00 → 02 → 20 → 01 →
11 → 10 → 00 → 01 → 12 → 22 →
21 → 10 → 01 → 10 → 02 → 22. When
we read off the labels of the associated
edges in order, we obtain the de Bruijn
sequence from B(3,3) previously
mentioned:
021112120002011001221010222.
Table of Contents
4 De Bruijn Graphs
A Special De Bruijn Sequence for the SET Deck
Consider the alphabet A = {0, 1, 2}. We can interpret each SET card as a
string of length n = 4 over the alphabet A, which has k = 3 elements. The
following table provides a mapping between such strings and SET cards.
Provide context to alphabet A
For instance, the string 0000 refers to the card with three, purple, striped
diamonds
Using this encoding, any de Bruijn sequence from B(3, 4) allows us to read
off (cyclically) all 81 consecutive subsequences (from left to right)
producing an order of the deck necessary to perform our trick.
Based on this construction, every four consecutive digits of the sequence
provide full information for one card and partial information for the three
cards after it.
Do we have to memorize the entire sequence of length 81?
Do we have to memorize the entire sequence of length 81?

Luckily, no.
It turns out that there are some de Bruijn sequences with nice algebraic
properties, giving us an ability to “predict” the sequence beyond a given
substring in order to perform the trick without needing to memorize all the
terms of the sequence.
Definition
We define our de Bruin sequence B = (0, 0, 0, 1, B5 , B6 , . . . , B81 ) where Bn
(for n > 4) is obtained recursively by Bn−3 + Bn−4 (mod 3). Thus, given
any consecutive substring of the form Bn Bn+1 Bn+2 Bn+3 , the next entry
Bn+4 is the remainder of the sum Bn + Bn+1 when divided by 3.
We will start with 0001, then the fifth digit is 0 + 0 (mod 3) = 0, the
sixth digit is 0 + 0 (mod 3) = 0, and the seventh digit is 0 + 1
(mod 3) = 1. By continuing this recursive process, we end up with a
complete de Bruijn sequence of length 81:
The Recursive de Bruijn Sequence for “In Tetracycles”

B = 0001001101211002102012210101111222011212000200
22021220012010211202022221110221210
Table of Contents
4 De Bruijn Graphs
Preparation
Arrange the deck in a specific order based on our de Bruijn sequence.

B = 0001001101211002102012210101111222011212000200
22021220012010211202022221110221210
Preparation
Arrange the deck in a specific order based on our de Bruijn sequence.

0001 would be the first card, and 0010 would be the second and so
on.

B = 0001001101211002102012210101111222011212000200
22021220012010211202022221110221210
Performance
The magician cuts the deck repeatedly (since it is cyclic, the property
of de Bruijn sequence remains).
Performance
The magician hands out four consecutive cards to four volunteers.
Performance
The magician asks ”Which feature would you four like to describe?”
Let us assume the volunteers choose shape.
Performance
The magician then asks ”Would all of you holding the diamond please
raise your hand?” Let us assume the third person raises their hand.
Performance
The magician asks ”Now, would everyone with an oval please raise
your hand?” Let us assume the first and fourth person raise their
hand.
Performance
The magician asks ”Now, would everyone with an oval please raise
your hand?” Let us assume the first and fourth person raise their
hand.
The magician correctly name all four cards in order, including their
numbers, colors, shadings, and shapes.
Trick Reveal
We deduct that the one volunteer

that did not raise the hand must
have a card with squiggle shape.
Trick Reveal

The order “Oval, Squiggle,
Diamond, Oval” corresponds to
1201.
Trick Reveal

The order “Oval, Squiggle,
Diamond, Oval” corresponds to
1201.
Since shape is the last feature in our
table, to know the complete
information of all four cards, we
need to go backwards and deduct
Bi Bi+i Bi+2 1201.
Trick Reveal
By our recursive definition, we have:
Bi+6 − Bi+3 = 1 − 1 = 0, so
Bi+2 = 0
Bi+5 − Bi+2 = 0 − 0 = 0, so
Bi+1 = 0
Bi+4 − Bi+1 = 2 − 0 = 2, so
Bi = 2
Trick Reveal
By our recursive definition, we have:
Bi+6 − Bi+3 = 1 − 1 = 0, so
Bi+2 = 0
Bi+5 − Bi+2 = 0 − 0 = 0, so
Bi+1 = 0
Bi+4 − Bi+1 = 2 − 0 = 2, so
Bi = 2
Thus, we have an entire length
seven subsequence of the form
2001201, from which we can read
off the algebraic representation of
each card in order.
Trick Reveal
The sequence 2001201 provides us

complete information of the four
cards that the volunteers are
holding:
1st card is 2001
2nd card is 0012
3rd card is 0120
4th card is 1201
By applying the table and match
each number with its corresponding
properties, we obtain the four cards
on the left, thus complete the trick.
Wrap Up and Further Reading
In TetraCycles is a variation on the In Cycles trick developed by Persi

Diaconis and Ron Graham and elaborated in their book Magical
Mathematics: The Mathematical Ideas That Animate Great Magic Tricks
(2015). Reading Chapter 3 on “Univerisal Cycles” got us started on this
exploration. We dedicate this work to the mathematical legacy of Dr.
Ronald Graham.
I would also like to thank Professor Parker Glynn-Adey at the University of
Toronto Mississauga for supervising the summer research, as well as
Doctor Tom Edgar, editor of Mathematical Association of America for his
constant input and beautiful de Bruijn graphs.

A Magic Trick Using The SET Deck: Zhengyu Li

Uploaded by

Copyright:

Available Formats

A Magic Trick Using The SET Deck: Zhengyu Li

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

A Magic Trick Using The SET Deck: Zhengyu Li

Uploaded by

Copyright:

Available Formats

A Magic Trick Using the SET Deck

Department of Mathematical and Computational Sciences

Canadian Undergraduate Mathematics Conference, August 2020

1 Quick Intro of SET

3 De Bruijn Sequences and Its Special Properties

5 A Special De Bruijn Sequence for the SET Deck

6 The “In TetraCycles” Trick Reveal

1 Quick Intro of SET

3 De Bruijn Sequences and Its Special Properties

5 A Special De Bruijn Sequence for the SET Deck

6 The “In TetraCycles” Trick Reveal

The deck consists of 81 unique cards.

The deck consists of 81 unique cards.

The deck consists of 81 unique cards.

The deck consists of 81 unique cards.

1 Quick Intro of SET

3 De Bruijn Sequences and Its Special Properties

5 A Special De Bruijn Sequence for the SET Deck

6 The “In TetraCycles” Trick Reveal

1 Quick Intro of SET

3 De Bruijn Sequences and Its Special Properties

5 A Special De Bruijn Sequence for the SET Deck

6 The “In TetraCycles” Trick Reveal

1 Quick Intro of SET

3 De Bruijn Sequences and Its Special Properties

5 A Special De Bruijn Sequence for the SET Deck

6 The “In TetraCycles” Trick Reveal

1 Quick Intro of SET

3 De Bruijn Sequences and Its Special Properties

5 A Special De Bruijn Sequence for the SET Deck

6 The “In TetraCycles” Trick Reveal

Do we have to memorize the entire sequence of length 81?

Do we have to memorize the entire sequence of length 81?

The Recursive de Bruijn Sequence for “In Tetracycles”

1 Quick Intro of SET

3 De Bruijn Sequences and Its Special Properties

5 A Special De Bruijn Sequence for the SET Deck

6 The “In TetraCycles” Trick Reveal

Arrange the deck in a specific order based on our de Bruijn sequence.

The Recursive de Bruijn Sequence for “In Tetracycles”

Arrange the deck in a specific order based on our de Bruijn sequence.

The Recursive de Bruijn Sequence for “In Tetracycles”

We deduct that the one volunteer

We deduct that the one volunteer

We deduct that the one volunteer

By our recursive definition, we have:

By our recursive definition, we have:

The sequence 2001201 provides us

In TetraCycles is a variation on the In Cycles trick developed by Persi

You might also like