Maths Olympiad Prep

Library / /142 of 144

Combinatorics Difficulty 9.1 IMO level Find the answer

Players AA and BB play a game on a blackboard that initially contains 2020 copies of the number 1 . In every round, player AA erases two numbers xx and yy from the blackboard, and then player BB writes one of the numbers x+yx+y and xy|x-y| on the blackboard. The game terminates as soon as, at the end of some round, one of the following holds:
[list]
[*] (1)(1) one of the numbers on the blackboard is larger than the sum of all other numbers;
[*] (2)(2) there are only zeros on the blackboard.
[/list]
Player BB must then give as many cookies to player AA as there are numbers on the blackboard. Player AA wants to get as many cookies as possible, whereas player BB wants to give as few as possible. Determine the number of cookies that AA receives if both players play optimally.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to carefully analyze the game dynamics and the optimal strategies for both players, A A and B B .

Initially, the blackboard contains 2020 copies of the number 1. The players' moves involve manipulating these numbers under certain rules:

1. Player A A erases two numbers, x x and y y .
2. Player B B then writes either x+y x+y or xy |x-y| back on the blackboard.

The game ends under two conditions:
- One number becomes larger than the sum of all others.
- All numbers become zero.

To find the optimal strategies for both players:

### Analyzing the Strategies:

- **Player A A Strategy:**
- Player A A aims to keep the game going for as long as possible to maximize the number of cookies received. A A will look to choose x x and y y such that the choices available to B B either do not terminate the game quickly or lead to suboptimal reductions.

- **Player B B Strategy:**
- Player B B wants to end the game as soon as possible to minimize the number of numbers on the blackboard, thus minimizing the cookies given away. Therefore, B B tries to quickly reach one of the stopping conditions, preferably making all numbers zero.

### Evaluating the Outcome:

Given the 2020 starting numbers:

1. Game Dynamics:
- Each operation by the two players reduces the total number of numbers on the board by exactly one each round.
- If m m is the total number of operations performed, then the number of entries on the blackboard at the end of the game is 2020m 2020 - m .

2. Equalizing Strategy:
- Player B B can minimize the number of cookies by trying to ensure that the numbers gradually reduce to an equal or nearly equal state, especially driving towards zeroes by cleverly using the xy |x-y| operation whenever possible.

3. Optimal Play:
- Player B B can achieve a situation where only 7 numbers remain on the blackboard through optimal reduction strategies despite the initial large number of 1s because:
- Using the x+y x+y or xy |x-y| operation strategically can quickly consolidate numbers or eliminate non-zero numbers.

Given the optimal plays from both sides, the minimum number of numbers left on the board—and hence cookies to be given—is 7 after the conclusion of their strategies.

Thus, the number of cookies player A A receives is:
7. \boxed{7}.

This solution reflects the balance between both players playing optimally to achieve their conflicting goals.

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