Problem:
Alice and Barbara have invented the following game. They have a grid, with the cells numbered from to from left to right, and tiles also numbered from to . The game begins with the grid empty, and the two players alternate making moves; the player whose turn it is may choose between:
- selecting a tile not yet placed on the grid and placing it on an empty cell, provided that the numbers on the placed tiles, read from left to right, are in increasing order;
- selecting a tile already placed on the grid and moving it to an adjacent cell so that the tile gets closer to the cell bearing the same number as the tile, provided that the destination cell is free (example: if the tile numbered is on cell number , it may be moved to the left, but not to the right; if instead a tile is already on the cell with its own number, it can no longer be moved).
(a) Prove that at each turn, if the tiles are not all on the grid, there exists a legal move.
(b) If Alice starts and the winner is the one who places the last tile, who has a winning strategy?