Tuesday, 30 November 2010

Card Trick Leads to New Bound on Data Compression - Technology Review

Here's a card trick to impress your friends. Give a deck of cards to a pal and ask him or her to cut the deck, draw six cards and list their colours. You then immediately name the cards that have been drawn.
Magic? Not quite. Instead, it's the next best thing: mathematics. The key is to arrange the deck in advance so that the sequence of the card colours follows a specific pattern called a binary De Bruijn cycle. A De Bruijn sequence is a set from an alphabet in which every possible subsequence appears exactly once.
So when a deck of cards meets this criteria, it uniquely defines any sequences of six consecutive cards. All you have to do to perform the trick is memorise the sequences.
Usually these kinds of tricks come about as the result of some new development in mathematical thinking. Today, Travis Gagie from the University of Chile in Santiago turns the tables. He says that this trick has led him to a new mathematical bound on data compression....

Neat!! I love how maths integrates with life..
wonder how would this be used 5 years down..

The actual paper is here
Ref: arxiv.org/abs/1011.4609: Bounds from a Card Trick

No comments:

Post a Comment

Datanami, Woe be me