Track / Stage 7 / 227 of 300 #1627 of 2000

Problem 1627

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.5 Find the answer

Alphonse and Beryl are playing a game. The game starts with two rectangles with integer side lengths. The players alternate turns, with Alphonse going first. On their turn, a player chooses one rectangle, and makes a cut parallel to a side, cutting the rectangle into two pieces, each of which has integer side lengths. The player then discards one of the three rectangles (either the one they did not cut, or one of the two pieces they cut) leaving two rectangles for the other player. A player loses if they cannot cut a rectangle.

Determine who wins each of the following games:

(a) The starting rectangles are $1 \times 2020$ and $2 \times 4040$ .
(b) The starting rectangles are $100 \times 100$ and $100 \times 500$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

To determine who wins each of the given games, we need to analyze the possible moves and outcomes for each player. The key is to identify the losing positions, i.e., positions from which the player to move cannot make a valid cut.

### Part (a): The starting rectangles are $1 \times 2020$ and $2 \times 4040$ .

1. Initial Position: The rectangles are $1 \times 2020$ and $2 \times 4040$ .

2. Possible Moves:
- Alphonse can cut the $1 \times 2020$ rectangle into two smaller rectangles, say $1 \times k$ and $1 \times (2020 - k)$ , and discard one of the resulting rectangles.
- Alphonse can cut the $2 \times 4040$ rectangle into two smaller rectangles, say $2 \times m$ and $2 \times (4040 - m)$ , and discard one of the resulting rectangles.

3. Losing Positions:
- A player loses if they cannot make a valid cut. This happens when both rectangles are $1 \times 1$ or $2 \times 1$ (since these cannot be cut further).

4. Analysis:
- If Alphonse cuts the $1 \times 2020$ rectangle, he can always leave a $1 \times k$ rectangle and a $2 \times 4040$ rectangle for Beryl.
- If Alphonse cuts the $2 \times 4040$ rectangle, he can always leave a $2 \times m$ rectangle and a $1 \times 2020$ rectangle for Beryl.

5. Strategy:
- Alphonse can always make a cut that leaves Beryl with two rectangles that can still be cut. Therefore, Alphonse has a winning strategy.

### Part (b): The starting rectangles are $100 \times 100$ and $100 \times 500$ .

1. Initial Position: The rectangles are $100 \times 100$ and $100 \times 500$ .

2. Possible Moves:
- Alphonse can cut the $100 \times 100$ rectangle into two smaller rectangles, say $100 \times k$ and $100 \times (100 - k)$ , and discard one of the resulting rectangles.
- Alphonse can cut the $100 \times 500$ rectangle into two smaller rectangles, say $100 \times m$ and $100 \times (500 - m)$ , and discard one of the resulting rectangles.

3. Losing Positions:
- A player loses if they cannot make a valid cut. This happens when both rectangles are $100 \times 1$ or $1 \times 100$ (since these cannot be cut further).

4. Analysis:
- If Alphonse cuts the $100 \times 100$ rectangle, he can always leave a $100 \times k$ rectangle and a $100 \times 500$ rectangle for Beryl.
- If Alphonse cuts the $100 \times 500$ rectangle, he can always leave a $100 \times m$ rectangle and a $100 \times 100$ rectangle for Beryl.

5. Strategy:
- Alphonse can always make a cut that leaves Beryl with two rectangles that can still be cut. Therefore, Alphonse has a winning strategy.

Conclusion:
In both cases, Alphonse has a winning strategy because he can always make a cut that leaves Beryl with two rectangles that can still be cut.

The final answer is Alphonse wins both games.

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