A Card Trick Leads To A New Mathematical Bound On Data Compression

“A complicated card trick that deals with the colors of the cards and a binary De Bruijn cycle has helped a mathematician reach a new bound on data compression. Magic and math, more friendly than you’d think!

Here’s how the trick works: You hand your friend a deck of cards and ask them to draw six cards (in order) and name the colors. With that sequence of colors, you can immediately name the exact cards that have been drawn. How? Because each color sequence is unique and appears only once throughout the deck (after pre-arranging it to be so), so if you have an insane memory, you’ll know which cards correspond to the sequence.

According to Travis Gagie from the University of Chile in Santiago, the trick is closely related to data compression:

“Gagie achieves this new [mathematical] bound by considering a related trick. Instead of pre-arranging the cards, you shuffle the pack and then ask your friend to draw seven cards. He or she then lists the cards’ colours, replaces them in the pack and cuts the deck. You then examine the deck and say which cards were drawn. This time you’re relying on probability to get the right answer. “It is not hard to show that the probability of two septuples of cards having the same colours in the same order is at most 1/128,”
This turns out to be closely related to various problems of data compression and leads to a lower bound than has been found by any other means.”"

Read more at Gizmodo