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.
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.
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!
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!
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].
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 ♦, 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 ♠.
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.