Maths Olympiad Prep

Library / /323 of 520

Combinatorics Difficulty 5.7 AIME, harder Prove it

[Winning and Losing Positions]

Fili and Kili are playing chess. Besides the chessboard, they have one rook, which they placed in the bottom-right corner, and they take turns moving it, but they are only allowed to move it up or to the left (by any number of squares). The player who cannot make a move loses. Kili moves first. Who will win with correct play?

Solution

The one who moves second, that is, Fil, will win. For this, after each move by Kili, Fil needs to move the rook back to the main diagonal leading from the bottom right corner to the top left. In this case, after each move by Fil, the rook will be on this diagonal, and higher than after the previous move by Fil. This means that sooner or later, after a move by Fil, the rook will end up in the top left corner, which means Kili will have no legal moves left.

## Answer

Fil will win.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.