Card games and AVG-based Robotic Navigation

I will start with a card game that I found in the book 'Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks' by Persi Diaconis and Ron Graham:" A magician (read mathematician) selects five spectators by some random process (say throwing five balls blindfolded), Then he gives the first spectator a deck of cards and asks him to cut the deck and take card.from the top. Then the second one is asked to pick up the next card, the third one the next, the fourth one the next, and the last one the next card from top. The spectators are asked not to show their cards to the magician and to concentrate on their own cards. The magician waves his hands a bit and then asks them who of them are holding red cards. He again waves his hands a bit, closes his eyes, and then correctly declares the names of the cards that each spectator is holding, and in correct order."

Now we shall see how the trick works. Clearly, the key to the trick lies in the question on people having red cards. Further, notice that 5 cards have been distributed, which means 5 bits of information, each bit being either "Red"(1), or "Black"(0). Knowing the "Red" (or "Black") bits, one can completely frame the 5-bit sequence of information. Clearly, there are ${ 2 }^{ 5 }=32$ such possible sequences which indicates that the deck has 32 cards instead of 52. Also, notice that if these 32 cards are given an order (i.e., a permutation), the order remains invariant under the operation of cutting the deck (note that the deck is being cut, not shuffled). So, the cutting does nothing to the order in which the magician has arranged the deck. Finally observe that the magician tells the 5 cards only knowing their color sequence. This indicates something sneaky. Replace the 32 cards by a 32-bit sequence of information in 1's(Reds) and 0's(Zero's). So, the above feat can only be accomplished if every 5 consecutive bits of this sequence is a unique sub-sequence. Suppose the 5-bit sub-sequence is 11010. Knowing this sub-sequence, the magician can tell what the cards are, since he knows that the sub-sequence occurs only once in the 32-bit sequence. And that shows how the trick works. (I have not explained how the magician remembers all the cards in order, that he does by waving his hands..its another type of Maths called Linear Feedback Shift Register.)

But my talk is not over yet. In fact, it has just begun. This trick brings out a new type of finite sequence. Named De Bruijn sequence after its discoverer, this type of sequence has a special property. A binary De Bruijn sequence B(k,n) of order n, is a cyclic sequence A of characters (or bits) of size k (size doesn't mean total length, it means number of different characters), such that every possible sub-sequence of length n of consecutive characters in A occurs exactly once in A. Eg. $0000100110101111$ is a binary De Bruijn Sequence of order 4. Using Graph Theory, and concepts of Eulerian circuits and Eulerian paths, we can prove that De Bruijn sequence B(k,n) can be constructed for any positive integers k and n, and length of such sequence is ${ k }^{ n }$.

Now that we have got a basic idea about De Bruijn Sequences, we can generalize the concept to De Bruijn Arrays or Matrices. A k-ary De Bruijn Array A(k,m,n) of order $m\times n$ is an array that has size k, and every $m\times n$ sub-array of it (formed by adjacent elements) occurs only once in this array. However, that a De Bruijn Sequence exists for any natural k,m and n has yet not been proved theoretically. May be that some of you may prove it one day. But just like the laws of thermodynamics, or the Schrodinger's Equation, or the Riemann Hypothesis, this is assumed to be true as no contradictory examples to this hypothesis have been found yet.

This hypothesis, if proved, can be a revolutionary result, since it can be used in Global Positioning from Local Information by Robots in future. The whole surface of the earth can be mapped into a large spherical k-ary De Bruijn Array of order $m\times n$ where m and n are small and k is very very big. A robot will have sensors attached to its feet that scan any $m\times n$ sub-array which falls under its feet. Since the sub-array occurs only once in the whole array, the robot searches its directories and finds the location of the sub-array in the array and thus finds its position. Interesting link between a card game and AVG robotics, isn't it?