# A magic trick with synchronizing words

See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html

Believe it or not, the lady didn't really read your mind; she is not even a real lady but a computer that used a principle in mathematics called synchronizing words. http://en.wikipedia.org/wiki/Synchronizing_word

That trick was done with 25 flags. I think it would be neat if I could do it with a lot more flags, but at the same time I wouldn't want the spectator to get bored with lots of instructions.

Is there a good way to do this with say 200 flags with only one or two more instructions? How about 1,000 flags?

-
If you make for example green flags very rare it doesn't matter that the total amount of flags is huge.. (if you let the user begin with a green flag for example) – Listing Jan 23 '12 at 18:26
True, but I don't want to make it too obvious. – Craig Feinstein Jan 23 '12 at 18:32
Also, I would like it so that the person has a free choice of where to start, unlike the demo, where you could only start on blue flags. – Craig Feinstein Jan 23 '12 at 18:34
The lady is very creepy. Her face and the music made me feel that at some point it was gonna be a "scary yelling spooky pop-up" like we all hate them. I must say I don't understand all the downvotes, OP asked for a perfectly legitimate question. – Patrick Da Silva Jan 23 '12 at 18:38
@Patrick Da Silva, Maybe the down-votes were because it's Applied Mathematics :-) – Craig Feinstein Jan 23 '12 at 19:29

Since this is an applied question, I might suggest an applied answer (perfectly legitimate question, though). Finding the synchronizing word is an NP-complete problem. I'm not sure if an elegant, purely mathematical solution exists, because it requires you to factor in your available classes of flags as well.

The actual problem comes down to arranging the flags according to the instructions you are going to give the user. You could use dynamic programming to push the flags into a DAG, based on the inverse of your conditions, then walk the DAG to produce the possible set of flags.

-

Limiting the number of instructions, will always make it easier to recognize, if it is repeated by the 'player'

One way to eliminate this, is to use different instructions, having multiple sets of paths is not only possible, but would make the illusion more effective.

I would say that having a small number of green, or yellow, or even calling for mixed color flags with multiple synchronizing paths would be my solution.

-