7
$\begingroup$

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

Spoiler Alert

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?

  • 2
    @Patrick Da Silva, Maybe the down-votes were because it's Applied Mathematics :-)2012-01-23

2 Answers 2

1

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.

1

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.