Given an $m \times n$ table consisting of $mn$ unit cells. Alice and Bob play the following game: Alice goes first and the one who moves colors one of the empty cells with one of the given three colors. Alice wins if there is a figure, such as the ones below, having three different colors. Otherwise Bob is the winner. Determine the winner for all cases of $m$
and $n$ where $m, n \ge 3$.
Proposed by Toghrul Abbasov, Azerbaijan
I claim that for $m \ge 5, n \ge 4$ ( or reversed, since it is a rotation anyways) Alice has a winning strategy, otherwise Bob has. Here is the proof:
First, name cells as $c_{ij}$ where $i$ shows the row number and $j$ shows the column number.
Lemma 1: Alice has to start from the cells to the neigbour to the sides where it can make more possible figures. Because after Bob plays, his move will make new possible figures. For the exact reason, Bob has to play on the cells of the sides since it will make less possible figures to make. If Alice can't force Bob to make new possible figures, Bob wins, since he can counter all the possible figures
We will prove that Alice will win for the case $m=5, n=4$. Since bigger cases still can be played in this case, The bigger values will be proven. We will show a algorithm for Alice.
Let 3 colors be Red,Green and blue. For notations, we will show colored cells as $c_{ij}^r$ , $c_{ij}^g$ or $c_{ij}^b$.
Here is the algorithm (The colors can be changed and the sequence can be flipped, doesn't matter since symmetry): $c_{3,1}^b - c_{5,3}^b- c_{1,3}^r-c_{2,2}^r- c_{3,3}^g$
It is obvious that Alice wins whatever Bob does. Bob played $c_{5,3}$ instead of $c_{4,2}$ , it doesn't matter since all of these two makes the same number of possible figures. \newline
From Lemma 1, for cases $m=3, n \ge 3$ ( or reversed, it is a rotation), Bob will win. Since Alice can't force Bob to make new figures.
For the case $m=n=4$. It is the same idea as $m=3, n \ge 3$, since Alice cant force Bob to make more possible figures. ( The reason $m=5,n=4$ is winnable is Alice can force Bob to make 2 more figures.), Hence we are done