Maths Olympiad Prep

Track / Stage 7 / 18 of 300 #1418 of 1964

Problem 1418

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.0 Find the answer

Two players play the following game: alternatively they write numbers 11 or 00 in the vertices of an nn-gon.
First player starts the game and wins if after any of his moves there exists a triangle, whose vertices are three consecutive vertices of the nn-gon, such that the sum of numbers in it's vertices is divisible by 33.
Second player wins if he prevents this.
Determine which player has a winning strategy if:
a) n=2019n=2019
b) n=2020n=2020
c) n=2021n=2021

The source for this one didn't record the answer, so there is nothing to check what you type against. Work it on paper and mark yourself against the solution below.

Official solution

Let's analyze the game for each value of n n given in the problem.

### Case a) n=2019 n = 2019

1. **Determine the parity of n n **:
n=2019(odd) n = 2019 \quad \text{(odd)}
Since n n is odd, the first player A A will make the last move.

2. **Strategy for player A A **:
- Player A A starts by writing a 1.
- Player B B must write a 0 to prevent A A from winning immediately.
- Player A A continues by writing a 0.
- Player B B must write a 1 to prevent A A from winning immediately.

This pattern continues, and the sequence of numbers will be:
1,0,0,1,1,0,0,1,,1,0,0,1,1 1, 0, 0, 1, 1, 0, 0, 1, \ldots, 1, 0, 0, 1, 1

3. **Winning condition for player A A **:
- After A A 's last move, the sequence will have a pattern where there are three consecutive vertices with the same number (either 1 or 0).
- For example, the first, second, and (2k+1)(2k+1)-th vertices will form a triangle with the sum divisible by 3.

Thus, player A A has a winning strategy when n=2019 n = 2019 .

### Case b) n=2020 n = 2020

1. **Determine the parity of n n **:
n=2020(even) n = 2020 \quad \text{(even)}
Since n n is even, the second player B B will make the last move.

2. **Strategy for player B B **:
- Player A A starts by writing a 1.
- Player B B writes a 0 to prevent A A from winning immediately.
- Player A A continues by writing a 0.
- Player B B writes a 1 to prevent A A from winning immediately.

This pattern continues, and the sequence of numbers will be:
1,0,0,1,1,0,0,1,,1,0,0,1,1 1, 0, 0, 1, 1, 0, 0, 1, \ldots, 1, 0, 0, 1, 1

3. **Winning condition for player B B **:
- Player B B ensures that there are no three consecutive vertices with the same number.
- Since B B makes the last move, A A cannot form a triangle with the sum divisible by 3.

Thus, player B B has a winning strategy when n=2020 n = 2020 .

### Case c) n=2021 n = 2021

1. **Determine the parity of n n **:
n=2021(odd) n = 2021 \quad \text{(odd)}
Since n n is odd, the first player A A will make the last move.

2. **Strategy for player A A **:
- Player A A starts by writing a 1.
- Player B B must write a 0 to prevent A A from winning immediately.
- Player A A continues by writing a 0.
- Player B B must write a 1 to prevent A A from winning immediately.

This pattern continues, and the sequence of numbers will be:
1,0,0,1,1,0,0,1,,1,0,0,1,1 1, 0, 0, 1, 1, 0, 0, 1, \ldots, 1, 0, 0, 1, 1

3. **Winning condition for player A A **:
- After A A 's last move, the sequence will have a pattern where there are three consecutive vertices with the same number (either 1 or 0).
- For example, the first, second, and (2k+1)(2k+1)-th vertices will form a triangle with the sum divisible by 3.

Thus, player A A has a winning strategy when n=2021 n = 2021 .

The final answer is:

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