Maths Olympiad Prep

Library / /16 of 22

Combinatorics Difficulty 6.5 National Olympiad Prove it Italy

Problem:

Alice and Barbara have invented the following game. They have a 1×20181 \times 2018 grid, with the cells numbered from 11 to 20182018 from left to right, and 20182018 tiles also numbered from 11 to 20182018. 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 77 is on cell number 1212, 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?

Solution

Solution:

(a) If C1C_{1} is free, T1T_{1} can be moved to the left or placed on C1C_{1}, depending on whether it is already on the grid or not; the same reasoning applies to C2018C_{2018}, so from now on we will assume that C1C_{1} and C2018C_{2018} are both occupied. Having chosen a free cell CkC_{k}, let us call TaT_{a} and TbT_{b} the first tiles encountered starting from CkC_{k} and proceeding respectively to the left and to the right (hence a<ba < b): if kak \leq a one can move TaT_{a} to the right, just as if kbk \geq b one can move TbT_{b} to the left; finally, if a<k<ba < k < b, one can place TkT_{k} on CkC_{k}.

(b) We prove by induction on NN that, playing on a 1×N1 \times N grid, Alice has a winning strategy whose first move consists of placing T1T_{1} on CNC_{N} (or equivalently, if there is only T1T_{1} on CNC_{N} and it is Barbara's turn, Alice has a winning strategy).
If N=2N=2, Barbara must necessarily move T1T_{1} to C1C_{1}, after which Alice wins by placing T2T_{2} on C2C_{2}.
Now suppose that the claim holds for some N2N \geq 2 and that play takes place on a 1×(N+1)1 \times (N+1) grid: as before, Barbara must move T1T_{1} to CNC_{N}, and Alice can respond by placing TN+1T_{N+1} on CN+1C_{N+1}: since this last tile can no longer be moved, the rest of the game will take place on the 1×N1 \times N grid obtained by excluding CN+1C_{N+1} (and one easily observes that the presence or absence of CN+1C_{N+1} does not affect the set of legal moves). On this grid, after the moves described, there is only T1T_{1}, which is on CNC_{N}, and it is Barbara's turn, but by the induction hypothesis this configuration is favorable to Alice.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.