De Bruijn Sequence and Universal Cycle Constructions

The classic Atari game Pitfall applied an 8-stage linear feedback shift register (LFSR) to generate 255 different map locations that Harry could travel in the jungle. Each 8-bit binary string (missing the all 0 string) represented a unique location that included snakes, scorpions, alligators, and different types of treasures.

   

A nice discussion is provided in this blog post and this ASCII version of the game. For more, see Retrogame Archeology.

Interestingly, hundreds of Nintendo games applied the same 15-bit LFSR associated with the primitive polynomial $x^{15} + x^{7} + 1$ using machine code that comes in more than one hundred variants [TW22]. Unfortunately, most games devoted more memory to the LFSR’s state than necessary: Donkey Kong (1983) used 8 bytes (or 8 · 8 = 64 bits), The Legend of Zelda (1986) used 13 bytes, and Super Mario Bros 3 (1988) used 9 bytes. In each case, additional entropy is lost by a simple programming error: the bits are shifted in the wrong direction.

Consider an autonomous vehicle with limited sensors and power. It operates underground on a cyclic track, and its position is determined by scanning a length $n$ window of coloured squares (see P31 of [DG11]).

   

The longest possible track corresponds to a DB sequence. For a track of arbitrary length $m$, one must construct a cut-down DB sequence. If the vehicle can spin around, then to accurately decode its position and orientation from a window reading, the reversal of a window on the track should not appear as a possible window. For this case, one should construct an orientable sequence. This application naturally generalizes to two dimensions, giving rise to the study of planar maps and de Bruijn tori (also known as de Bruijn arrays).

An otherwise honest Prisoner is jailed for illegal gambling. The Warden, who also enjoys games of chance, offers the Prisoner a shot at freedom by presenting the following game. The Warden places 6 coins at random in front of the Prisoner. Each day either the Warden or the Prisoner will take the rightmost coin and add it to the beginning of the row, flipping the coin if they wish. If the coins all show Tails, the Prisoner goes free!

   

Game of Coins: All Tails, Prisoner goes free!

• If the rightmost coin shows Tails, the Warden makes the move.
• If the rightmost coin shows Heads, the Prisoner makes the move.

Given any starting configuration: Is there a winning strategy for the Prisoner? And if so, is there one that earns them their freedom in the least amount of time? Can the Warden keep the Prisoner indefinitely? And if not, is there a strategy that keeps the Prisoner jailed as long as possible?

Amazingly, optimal strategies for both the Prisoner and Warden correspond to following an appropriate prefix, depending on the starting configuration, of the greedy prefer-smallest (Granddaddy) DB sequence in reverse (where Heads=0, Tails=1); for optimal play, each player can apply the inverse of the successor rule for the Granddaddy DB sequence. Eventually, the Prisoner goes free.

After playing a few times, the Warden got bored and created a new game. This time, the Warden places 5 dice in front of their newest Prisoner. Each day either the Warden or the Prisoner will take the rightmost die and add it to the beginning of the row with some added restrictions. If the dice show all 6s, the Prisoner goes free!

Game of Dice: All 6s, Prisoner goes free!

• The Warden starts each day in control: They can move the rightmost die and decrease its value, or pass control to the Prisoner. If the die shows 1, they must pass.
• If the Prisoner gains control, they must move the rightmost die and either maintain or increase its value.

Again, optimal strategies for both the Prisoner and Warden correspond to following an appropriate prefix, depending on the starting configuration, of the greedy prefer-smallest (Granddaddy) DB sequence for $k=6$ in reverse (subtracting one from each die value); for optimal play, each player can apply the inverse of the successor rule for the Granddaddy DB sequence. Eventually, the Prisoner goes free.

Since the Granddaddy DB sequence is efficiently decodable, the Warden can choose a starting configuration to ensure that the Prisoner will remain jailed for a minimum amount of time. These games are introduced in [DiM18] with an alternate presentation for the binary case given in [Wei07]. See also [ARSW20,DiM19].

The following trick has been performed by renowned mathematicians Persi Diaconis and Ron Graham and is detailed in their book Magical Mathematics [DG11].

The cards: Consider a reduced deck of playing cards with only values Ace through 8. Each card can be assigned a unique bitstring of length $n=5$ as follows: The first two bits encode the suit (00 = ♣, 01 = ♠, 10 = ♦, and 11 = ♥) and the last three bits encode the value (000 = A, 001 = 2, ..., 111 = 8). Note the first bit provides the colour of the card (0=black, 1=red).

00000 = A ♣	01000 = A ♠	10000 = A ♦	11000 = A ♥
00001 = 2 ♣	01001 = 2 ♠	10001 = 2 ♦	11001 = 2 ♥
00010 = 3 ♣	01010 = 3 ♠	10010 = 3 ♦	11010 = 3 ♥
00011 = 4 ♣	01011 = 4 ♠	10011 = 4 ♦	11011 = 4 ♥
00100 = 5 ♣	01100 = 5 ♠	10100 = 5 ♦	11100 = 5 ♥
00101 = 6 ♣	01101 = 6 ♠	10101 = 6 ♦	11101 = 6 ♥
00110 = 7 ♣	01110 = 7 ♠	10110 = 7 ♦	11110 = 7 ♥
00111 = 8 ♣	01111 = 8 ♠	10111 = 8 ♦	11111 = 8 ♥

The setup: Order the cards based on your favourite DB-successor. Often the trick is described by applying an LFSR, but the DB-successor PCR4 is very easy to apply if you can distinguish necklaces quickly. Using PCR4, we get the (cyclic) DB sequence 00000111110111001100010110101001. Thus the cards are ordered:

A ♣, 2 ♣, 4 ♣, 8 ♣, 8 ♠, 8 ♥, 7 ♥, 6 ♥, 4 ♥, 8 ♦, 7 ♠, 5 ♥, 2 ♥, 4 ♦, 7 ♣, 5 ♠,
A ♥, 2 ♦, 3 ♣, 6 ♣, 4 ♠, 7 ♦, 6 ♠, 3 ♥, 6 ♦, 3 ♠, 5 ♦, 2 ♠, 3 ♦, 5 ♣, A ♠, A ♦.

The performance: Flash the audience the seemingly random sequence of cards. Then ask an audience member to cut the cards. Cut them again. Cut them again. (This does not affect the cyclic nature of the sequence!). Now lay out the first 5 cards in order, face down. The key information required is the colour of each card. Ask an audience member to look at the cards and report which ones are black=0. Also ask them several other unrelated questions for showmanship: What did you have for breakfast? Suppose, as an example, the cards are (red, black, red, red, black) = 10110. Thus, we already know the first card is 7 ♦. Now applying the simple successor rule PCR4 used to create the DB sequence we can predict the colour of the next 4 cards. A minor achievement leading up to the big reveal. Recommendation: use blank paper and pretend to record audience answers, when in fact you are calculating the colours. From our example, they will be 1010 = red, black, red, black. Using this information, we know the bit sequence from these 9 cards to be 101101010. Now amaze the audience by revealing the original 5 cards to be: 7 ♦, 6 ♠, 3 ♥, 6 ♦, 3 ♠.

A classic cipher lock application is from Fredricksen's survey [Fre82]:

   

Of course, the sequence required in this application is a DB sequence including the wraparound. For an interesting read on cracking such passwords see this blog post.