This summer my kids got a gift of a somewhat boring board game, where players were charged with tracing through a jumble of lines to find out what creature got to eat what dessert. The name escapes me now, and I escaped taking the game home, too.
But it was not all bad—the mechanics of the game made me google “permutation game” which came up with a fun puzzle (and annoying interview question; this phrasing is from a website that helps people cram for job interviews):
Alice and Bob play the following game:
They choose a permutation of the first numbers to begin with.
They play alternately and Alice plays first.
In a turn, they can remove any one remaining number from the permutation.
The game ends when the remaining numbers form an increasing sequence. The person who played the last turn (after which the sequence becomes increasing) wins the game.
Assuming both play optimally, who wins the game?
This game turns out to be kind of fun, at least if you find this sort of thing fun. I also tried a twist where we started with a string of letters, and crossed them off until they make a word.
Healthy Algorithms 