# 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?

Note by Kuldeep Guha Mazumder
5 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Thank you for sharing this!

Staff - 5 years, 6 months ago

I will try to post more of these notes..hope they are stimulating too..

- 5 years, 6 months ago

I would encourage you to also post problems related to these types of posts. This can often stimulate people's interest in a topic, and you can link to the note from the problem.

Additionally, you can add these ideas (or the relevant parts of them) to wiki pages, where they will be viewable by anyone who comes to the wiki!

For example, you could add some of this note to the Tricks section in Mind Reading. You can post on Slack chat if you have any questions.

Staff - 5 years, 6 months ago

I have added a section to the wiki that you have mentioned.

- 5 years, 6 months ago

The magician waves his hands a bit and then asks them a few questions including who of them are holding red cards.

This makes the entire thing very simple. "The magician asks them a few questions." One of them is who is holding the red cards; the other questions are what each card exactly is.

You should rephrase the story, saying that the magician only asks them a single question, namely who are holding red cards.

- 5 years, 6 months ago

Well observed. Let me correct it. Thanks!..:-)

- 5 years, 6 months ago