A quick game-theory puzzle to offer some distraction after the previous post:

There are 21 flags and two players, who alternate in taking turns to remove some flags. At each turn the player has to remove 1, 2, or 3 flags; this is the player’s choice at each move. The player who removes the last flag (whether as the sole remaining flag or one of the last surviving set of 2 or 3 flags) is the winner. Is there a winning strategy, and if so, what is it?No cheating now! By way of encouragement, let me say that the problem can be solved even without committing pen to paper - I know, as that's how I did.

You want to leave the other guy with four flags, that way whatever he picks you end up with the last flag. If you can leave him with multiples of four, he won't be able to flip it over to you, so if you're first, take one flag, if you're second hope that he takes 2 or 3 and leave him with 16.

Posted by: Frank McGahon | October 15, 2004 at 01:17 AM

Damn, that was quick! Tres bien, Monsieur.

Posted by: Abiola Lapite | October 15, 2004 at 01:19 AM

i worked backwards too, realizing that you must have 4 flags at the 2nd to last round, then 8,12,16,20 .

winning strategy for any player : make sure you leave a multiple of 4 after you've picked your flags.

of course if your adversary goes first and knows the strategy you're guaranteed to lose :)

winning strategy for any such games where you can pick any number of flags from [ 1 to (N-1)] : leave a multiple of N flags after your move and you should be able to win .

Posted by: ogunsiron | October 15, 2004 at 06:42 AM