Maths Olympiad Prep

Track / Stage 6 / 387 of 400 #1387 of 1964

Problem 1387

National olympiad, first round
Combinatorics Difficulty 6.9 Prove it

There is a m×(m1)m \times (m-1) board. (i.e. there are m+1m+1 horizontal lines and mm vertical lines) A stone is put on an intersection of the lowest horizontal line. Now two players move this stone with the following rules.
(i) Each players move the stone to a neighboring intersection along a segment, by turns.
(ii) A segment, which is already passed by the stone, cannot be used more.
(iii) One who cannot move the stone anymore loses.
Prove that there is a winning strategy for the former player.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Initial Setup: Consider a m×(m1)m \times (m-1) board, which has m+1m+1 horizontal lines and mm vertical lines. A stone is placed at an intersection on the lowest horizontal line.

2. First Move: The first player moves the stone up to point AA. This move effectively removes the bottom horizontal line from consideration, transforming the board into an m×mm \times m square.

3. **Rectangle ABCD\Box ABCD**: Consider a rectangle ABCD\Box ABCD inscribed in the m×mm \times m square, where the slopes of the lines forming the rectangle are either 11 or 1-1. This rectangle is formed by the diagonals of the square.

4. Movement Strategy: The first player can always keep the stone inside (including the borders of) ABCD\Box ABCD. This is because the first player can always move the stone to a neighboring intersection along a segment that has not been used before.

5. Vertex Degrees: In the rectangle ABCD\Box ABCD, every point except the vertices BB, CC, and DD has an even degree. This means that each of these points can be entered and exited an even number of times, ensuring that the stone can continue to move.

6. Parity Argument: The first player can always move to vertices BB, CC, or DD first due to the parity of moves. Since the first player starts the game, they will always have the advantage of making the first move to these critical points.

7. Winning Condition: By moving to BB, CC, or DD first, the first player ensures that the second player will eventually be unable to make a move, thus securing the first player's victory.

There is a winning strategy for the first player. \boxed{\text{There is a winning strategy for the first player.}}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.