Alice and Bob take turns to pick numbers from 1 thru 9, without replacement. The first to possess three distinct numbers that sum to 15 wins. Does Alice have a winning strategy?
From Peter Winkler's puzzles book.
Eight subsets of {1, 9} sum to 15. These are {1, 5, 9}, {2, 5, 8}, {3, 5, 7}, {4, 5, 6}, {1, 6, 8}, {2, 4, 9}, {2, 7, 6} and {3, 4, 8}. An insight into the structure of these eight possible subsets is helpful. The subsets can be laid out as a 3x3 magic square. The three rows, the three columns and the two diagonals of the magic square sum to 15 each.
2 | 7 | 6 |
9 | 5 | 1 |
4 | 3 | 8 |
The final insight is that Alice and Bob are simply playing tic-tac-toe on the magic square! So Alice does not have a winning strategy.