De Bruijn Sequence and Universal Cycle Constructions

Applications

DB sequences appeared as early as 400-200 BCE in Sanskrit prosody as a mnemonic aid in remembering all possible rhythms. In particular, the DB sequence (with wraparound) 01110100(01) was represented by the word yamátárájabhánasalagám where an accented vowel represents a 1 and an unaccented vowel represents a 0.

Video games

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.

Combinatorial games: Warden vs Prisoner

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 a 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 6's, the Prisoner goes free!

Game of Dice: All 6's, 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].

Card tricks

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 color 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 favorite DB-successor. Often the trick is described by applying a 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 color 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 color 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 colors. 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 ♠.

Cipher locks

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.

References

  • [DG11] P. Diaconis and R. Graham. Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks. Princeton University Press, 2011.

  • [DiM18] J. DiMuro. The warden’s de Bruijn sequence, 2018. arXiv:1807.09292v1

  • [Fre82] H. Fredricksen. A survey of full length nonlinear shift register cycle algorithms. Siam Review, 24(2):195-221, 1982.

  • [Wei07] G. Weiss. A combinatorial game approach to state nullification by hybrid feedback. In 2007 46th IEEE Conference on Decision and Control, pages 4643–4647, 2007.