Jump Snatch You are given a tic tac toe board and the following simple rules: you can jump a piece if it is between you and an empty square along any line, vertical, horizontal or digonal. When you jump a piece you remove it. In the solitaire version of this game, your goal is to have only one piece left after some number of jumps. Consider the following configuration (a dot means empty space) . x x . x x . . . Is there any way to ensure that only one piece will be left standing after some number of jumps. Solution: Sure. Start at the upper right corner. Down. Diagonal up left. Across right. Diagonal down left. Now for the questions: 1. How many spaces must you leave empty and where should they be in order to have only one piece remaining at the end? 2. Can you prove that this is the minimum? 3. If the tic-tac-toe board were 4 x 4, how many spaces must you leave empty and which one(s) to have only one remaining piece at the end? I don't know how to generalize these to larger squares. Also I don't know whether there exists a strategy that minimizes the number of initially empty spaces and which is "perfect" in the sense that the piece that first jumps is the only one that ever jumps and is the last one standing. All of this leads to the hardest game I know that is played on a 3 by 3 grid and that is extremely interesting on a 4 x 4 grid. Let's call it Jump-Snatch. Put pieces on all squares of the grid. The Snatcher removes a piece from any square he/she chooses. The Jumper then makes the first move after which moves alternate between Snatcher and Jumper until one player does a jump that leaves just one piece thereby winning. A move consists of jumping (after doing one jump, each additional jump is optional) if a jump is possible. If no jump is possible, then the move must consist of sliding a piece towards the center if possible. If that's not possible then the player may slide any piece in any direction. The figures below illustrate a 3 by 3 game. (jumpsnatch1.doc ... jumpsnatch8.doc) Who wins this game? Solutions: 1. For the 3 x 3 square, leaving 3 spaces empty works x x . x x x . x . Take the piece in the upper left hand corner and go all around and then through the diagonal. 2. Three empty spaces is the minimum, because no piece on the corner can get jumped, so at least three corners must be empty. 3. For the 4 x 4 square, you can start with one empty one and guarantee to have only one standing at the end. x x x x x . x x x x x x x x x x x x x x x x . . x x x x x x x x x x x x . . x . x x x x x x x x Now do the first, second and fourth columns just as the row above was done. . . x . . . x . x x x x . . x . Now jump up and left diagonally. . x x . . . . . x x x . . . x . . x x . . . x . x x . . . . . . . x x . . . x . . . x . . . . . Now, go back and forth with the upper-left piece and end as follows. . . . . . . . . . . . x . . . .