Question 75
Alice and Barbara have invented the following game. They have a $1 \times 2018$ grid, with the cells numbered from $1$ to $2018$ from left to right, and $2018$ tiles also numbered from $1$ to $2018$. The game starts with the grid empty, and the two players take turns making moves; the player whose turn it is can choose between:
- selecting a tile not yet placed on the grid and putting it on a free 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 moves closer to the cell bearing the same number as the tile, provided that the destination cell is free (example: if the tile with the number $7$ is on cell number $12$, it can be moved to the left, but not to the right; if instead a tile is already on the cell with its same number, it can no longer be moved).
(a) Prove that at every turn, if the tiles are not all on the grid, there exists a legal move.
(b) If Alice starts and whoever places the last tile wins, who has a winning strategy?
- selecting a tile not yet placed on the grid and putting it on a free 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 moves closer to the cell bearing the same number as the tile, provided that the destination cell is free (example: if the tile with the number $7$ is on cell number $12$, it can be moved to the left, but not to the right; if instead a tile is already on the cell with its same number, it can no longer be moved).
(a) Prove that at every turn, if the tiles are not all on the grid, there exists a legal move.
(b) If Alice starts and whoever places the last tile wins, who has a winning strategy?