A Card Trick Ends up in A New Mathematical Bound On Data Compression [Mathematics]

a sophisticated 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 may immediately name the exact cards which were drawn. How? Because each color sequence is unique and appears only once inside the deck (after pre-arranging it to be so), so in case 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 concerning data compression:

Gagie achieves this new [mathematical] bound by considering a related trick. Rather than 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 within the pack and cuts the deck. Then you definitely examine the deck and say which cards were drawn. This time you’re hoping on probability to get the perfect answer. ” It’s not hard to indicate that the probability of two septuples of cards having an identical colours within the same order is at most 1/128,”

This turns out to be closely relating to various problems of knowledge compression and ends up in a lower bound than has been found by any other means.

Magicians as mathematicians, I must have known. [ Technology Review ]

Source

This post is tagged: data compression, knowledge compression, mathematicians, perfect answer, university of chile