Let $k$ be a positive integer. Arnaldo and Bernaldo play a game in a table $2020\times 2020$, initially all the cells are empty. In each round a player chooses a empty cell and put one red token or one blue token, Arnaldo wins if in some moment, there are $k$ consecutive cells in the same row or column with tokens of same color, if all the cells have a token and there aren't $k$ consecutive cells(row or column) with same color, then Bernaldo wins. If the players play alternately and Arnaldo goes first, determine for which values of $k$, Arnaldo has the winning strategy.
Problem
Source: Brazil National Olympiad 2020
Tags: combinatorics
NTFEGAC
19.03.2021 00:30
I am sure that i have see this exercise before here.
bluelinfish
23.03.2021 22:10
bump? Does anybody have a solution or a link to where this was seen previously?
edfearay123
02.06.2021 21:19
I think that the answer is $k\leq 1011$. For a table $2n\times 2n$, the answer is $k\leq n+1$. For prove that Bernaldo wins when $k\geq n+2$, consider the following (For $2n=8$) \begin{tabular}{| c | c | c | c | c | c | c | c |} \hline & & & 9& & 9& & \\ \hline & & 10& &10 & & & \\ \hline 1 & & 3 &11 & 5&11 & 7& \\ \hline & 2 & 12& 4& 12& 6& & 8\\ \hline 1 & & 3 & 13& 5& 13& 7& \\ \hline & 2 & 14& 4& 14& 6& & 8\\ \hline & & &15 & &15 & & \\ \hline & & 16& & 16& & & \\ \hline \end{tabular} When Arnaldo puts a token in some cell with some number, Bernaldo puts a token with the other color in the cell that have the same number. Then it's easy to see that all $1\times 6$ or $6\times 1$ have two cells with tokens with different colors (Obviously also for $k\geq 6$), this because the form of the pairing. If Arnaldo puts token in cell without any number, Bernaldo puts token in cell without any number. For other values of $n$ we can make analogous pairing (it's a little difficult to explain here). We conclude that $k\geq n+2$, Bernaldo wins. Now, my conjeture is that Arnaldo wins for $k\leq n+1$, I think by induction, obviously if Arnaldo wins for some $k$ in $2n-2\times 2n-2$, then Arnaldo wins for the same $k$ in $2n\times 2n$. Then it would be enough to prove that for $k=n+1$ Arnaldo has the winning strategy (I thinking about it).
biomathematics
03.06.2021 10:08
We can number the table as follows (can be generalised): \begin{tabular}{| c | c | c | c | c | c |} \hline 1&1&3&4&5&5\\ \hline 2&2&3&4&6&6\\ \hline 7&8&9&9&11&12\\ \hline 7&8&10&10&11&12\\ \hline 13&13&15&16&17&17\\ \hline 14&14&15&16&18&18\\ \hline \end{tabular} With this numbering in mind, for each move of Arnaldo, Bernaldo can choose the cell with the same number as the one last chosen by Arnaldo and colour it with the colour not chosen by Arnaldo in Arnaldo's last move. This means that if $k \ge 5$ then Bernaldo wins.
starchan
13.07.2021 17:24
NTFEGAC wrote: I am sure that i have see this exercise before here. Quite similar to a USAMO problem on hexagonal cells and same type of a game.
wasikgcrushedbi
21.07.2023 15:10
biomathematics wrote: We can number the table as follows (can be generalised): \begin{tabular}{| c | c | c | c | c | c |} \hline 1&1&3&4&5&5\\ \hline 2&2&3&4&6&6\\ \hline 7&8&9&9&11&12\\ \hline 7&8&10&10&11&12\\ \hline 13&13&15&16&17&17\\ \hline 14&14&15&16&18&18\\ \hline \end{tabular} With this numbering in mind, for each move of Arnaldo, Bernaldo can choose the cell with the same number as the one last chosen by Arnaldo and colour it with the colour not chosen by Arnaldo in Arnaldo's last move. This means that if $k \ge 5$ then Bernaldo wins. How can you be sure that $k=4$ is achievable by Arnaldo?