Two players play the following game: alternatively they write numbers $1$ or $0$ in the vertices of an $n$-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 $n$-gon, such that the sum of numbers in it's vertices is divisible by $3$. Second player wins if he prevents this. Determine which player has a winning strategy if: a) $n=2019$ b) $n=2020$ c) $n=2021$
Problem
Source: Serbia JBMO TST 2021
Tags: combinatorics, Game Theory
04.01.2022 19:07
$A$ be first, $B$ be second player. For odd $n$ $A$ wins, but there are different strategies for $n\equiv 1\ (mod\ 4)$ and $n\equiv 3\ (mod\ 4)$. The idea is just forcing $B$ to write number to exactly $1$ place and exactly $1$ of numbers $(0,1)$. So for a) and c) $A$ wins. Bump for even $n$ (Probably $B$ wins,but bump anyway).
04.01.2022 22:01
B will win in $n$=even case. Call the vertices of the n-gon with no numbers on them as free points and those with numbers on them as busy points. Now suppose that A makes a move, and B has ensured before this move that there are only even number of free points between any 2 busy points. Now this move of A will make the free points odd between some 2 busy points odd. B's strategy is to write a number different from what A wrote, on a vertex adjacent to the vertex on which A wrote, on that side of it which has an odd number of free points between it and the nearest busy point. The full proof can now easily be completed.(basic idea here is that whenever A has to make a move, it always finds an even number of free points between any 2 busy points, also at least one of the neighboring vertices of any busy point must be busy when A has to make a move.)
06.01.2022 10:09
Call $A,B$ be the first and second person. It is true that whoever takes the last move wins. There is one obvious thing is that if $B$ wants to prevent $A$ from winning, $B$ has to choose the different number from $A$'s latest number, unless he will lose because $A$ can choose exactly that number he chooses from the previous step, so he can choose a triangle with 3 vertex 0's or 3 vertex 1's. WLOG, assume that $A$ will choose number 1 on his first move If $n=2k+1$ is odd, it means $A$ will take the last move. He can win this game by in each step, he choose the number that different from his previous number. And so by the rules, we will have the sequence of numbers they choose: $1,0,0,1,1,0,0,1,...,1,0,0,1,1$. Pick the $1^{st},2^{nd},(2k+1)^{th}$ vertex and $A$ is the winner. If $n=2k$ is even, it means $B$ will take the last move. He can win because whenever $A$ chooses any numbers and $B$ follows the rules, it is true that there are just maximum 2 consecutive numbers that have the same numbers, so $A$ can not choose any triples to win the game.
01.04.2024 07:22
Jalil_Huseynov wrote: $A$ be first, $B$ be second player. For odd $n$ $A$ wins, but there are different strategies for $n\equiv 1\ (mod\ 4)$ and $n\equiv 3\ (mod\ 4)$. The idea is just forcing $B$ to write number to exactly $1$ place and exactly $1$ of numbers $(0,1)$. So for a) and c) $A$ wins. Bump for even $n$ (Probably $B$ wins,but bump anyway).
CAN U PLS POST THE FULL SOLUTION OF IT
24.04.2024 14:16
$i)$ If $n$ is even, $B$ wins. $B$ divides the vertices into $\frac{n}{2}$ pairs and when $A$ writes a number on a vertex, $B$ writes the other number on its pair. $ii)$ If $n$ is odd, $A$ wins. Number the vertices as $1,2,...,n$. $A$ writes $1$ on the first vertex. Because we have $n\geq 7,$ at least one of the sets $\{2,3,4\}$ and $\{n-1,n-2,n-3\}$ will be empty. WLOG let $\{2,3,4\}$ be empty. $A$ writes $0$ on the fourth vertex. After this, $B$ cannot write any number between first and fourth vertices in order to win. But there are even number of vertices except $\{1,2,3,4\}$ and the other vertex where $B$ wrote in his first move since $n-5$ is even. Thus if $A$ doesn't write anything between $1$ and $5$ until $B$ writes, then $A$ wins.