Competition problem — Combinatorics

Library / /68 of 68

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Estonia

Integers $a$ , $b$ , $c$ and $n$ are given such that $1 \le a < b < c \le n$ . Juku and Miku play the following game on a strip of size $1 \times n$ : In the beginning, squares number $a$ , $b$ , $c$ contain one piece each, whereby the squares are numbered from the right to the left by consecutive integers starting from $1$ . On one's move, each player chooses one piece out of these three and shifts it one or more squares to the right. However, it is not allowed to move a piece to a square that contains another piece or jump over such a square; one also must not move a piece off the strip. Players move by turns, with Juku moving first. The player who cannot move loses. Which player can win regardless of the opponent's play?

Solution

Firstly, note that, in any position where the number of empty squares between the leftmost and the middle piece differs from the number of empty squares in the right from the rightmost piece, one can make a move that makes these two quantities equal. Indeed, if the number of empty squares between the leftmost and the middle piece is greater than the number of empty squares right from the rightmost piece then one can move the leftmost piece, otherwise one can move the rightmost piece.

Secondly, note that every move in any position where the number of empty squares between the leftmost and the middle piece equals the number of empty squares in the right from the rightmost piece makes these two quantities different. Indeed, moving either the leftmost or the middle piece changes the number of empty squares between the leftmost and the middle piece while leaving the empty squares right from the rightmost piece unchanged; when moving the rightmost piece, it is the other way round.

Consequently, Juku can win if $c - b \neq a$ by always moving in such a way that the number of empty squares between the leftmost and the middle piece were equal to the number of empty squares right from the rightmost piece after his move. As the sum of distances of all three pieces from the right edge of the strip decreases at each move, the game must eventually end and, by the considerations above, only Miku can lose. On the other hand, if $c - b = a$ then after Juku's move the number of empty squares between the leftmost and the middle piece differs from the number of empty squares right from the rightmost piece. Analogously to the previous case, Miku can win in this position.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.