MCS-236 extra credit

Varied due dates.

• (Extra credit #1) There are some card tricks magicians use which involve using de Bruijn sequences. Instead of using the alphabet {0,1} of size d=2 (as the book does) or {0,1,2} of size d=3 (as I did in class) they use the d=4 suits {Spades,Hearts,Diamonds,Clubs} or {S,H,D,C}. We wish to make a de Bruijn sequence of length 52 cards, so that if the magician sees (or is told by the audience) the suits of three consecutive cards (say Spades-Hearts-Hearts), she can predict the next card.
  1. The techniques we discussed in class can be used to make de Bruijn sequence of length greater than 52 where d=4 (for the four suits) and every string of length n=3 is represented. How long would the sequence be?

     I don't recommend drawing the whole Eulerian digraph to find this de Bruijn sequence, since it would look like a big mess. But list all the vertices of the digraph, and indicate a few of the edges. How many edges will the digraph have?

  2. Prove there is a de Bruijn sequence of length 52 using d=4 digits (the four suits) and string of length n=3 with the additional property that there there are 13 each of H's, S's, D's, and C's in the sequence. You don't need to actually write the sequence if you prove it exists. (Hint: The techniques to solve West 2.4.26 are a good starting point.)