Two players play the following game: alternatively they write numbers or in the vertices of an -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 -gon, such that the sum of numbers in it's vertices is divisible by .
Second player wins if he prevents this.
Determine which player has a winning strategy if:
a)
b)
c)
Problem 1418
Official solution
Let's analyze the game for each value of given in the problem.
### Case a)
1. **Determine the parity of **:
Since is odd, the first player will make the last move.
2. **Strategy for player **:
- Player starts by writing a 1.
- Player must write a 0 to prevent from winning immediately.
- Player continues by writing a 0.
- Player must write a 1 to prevent from winning immediately.
This pattern continues, and the sequence of numbers will be:
3. **Winning condition for player **:
- After '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 -th vertices will form a triangle with the sum divisible by 3.
Thus, player has a winning strategy when .
### Case b)
1. **Determine the parity of **:
Since is even, the second player will make the last move.
2. **Strategy for player **:
- Player starts by writing a 1.
- Player writes a 0 to prevent from winning immediately.
- Player continues by writing a 0.
- Player writes a 1 to prevent from winning immediately.
This pattern continues, and the sequence of numbers will be:
3. **Winning condition for player **:
- Player ensures that there are no three consecutive vertices with the same number.
- Since makes the last move, cannot form a triangle with the sum divisible by 3.
Thus, player has a winning strategy when .
### Case c)
1. **Determine the parity of **:
Since is odd, the first player will make the last move.
2. **Strategy for player **:
- Player starts by writing a 1.
- Player must write a 0 to prevent from winning immediately.
- Player continues by writing a 0.
- Player must write a 1 to prevent from winning immediately.
This pattern continues, and the sequence of numbers will be:
3. **Winning condition for player **:
- After '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 -th vertices will form a triangle with the sum divisible by 3.
Thus, player has a winning strategy when .
The final answer is: