$\textbf{Color the Grid}$
Two geniuses are playing a game of coloring a $2\times n$ grid where $n$ is an odd integer. Each of them in turn picks a uncolored cell and colors it in either green or red until all the cells are filled. At the end of the game, if the number of adjacent pairs with the same color is greater than the number of adjacent pairs with different colors, then the person who picks and colors first wins the game. (An adjacent pair consists of two cells next to each other.) Otherwise, if there are more adjacent pairs with different colors than those with same color, the person who starts later wins. If these two numbers are the same, the result is a tie. Who will win if both players make no mistake?
$\textbf{Solution}$
The person who starts later will win the game. A guaranteed winning strategy for him is to always pick the cell in the same column of the one picked by his opponent in the previous move. If this is an odd column, he will color it differently from what his opponent does. If this is an even column, he will color it the same as his opponent's choice. Then it can be shown that there will be always one more pair of different colored adjacent cells than the same-color pairs.
$\textbf{Analysis}$
There are in total $$2\times (n-1) + n = 3n - 2$$
pairs on a $2\times n$ grid because each row has $(n-1)$ pairs of adjacent cells and there are $n$ vertical pairs. Given $n$ is odd, the above number must be odd too. Hence, it is impossible for this game to result in a tier.
When $n=1$, it is clear that the late mover will win by coloring differently from the first mover. This also hints that the late mover has an advantage of having the option of choosing different colors based on his opponent's choice. Therefore, it is likely that the late mover may have a winning strategy.
The next simplest case is $n=3$ because $n$ must be odd. By the principle of symmetry, the middle column seems to be a good starting point for analysis. (Because $n$ is odd, there is always a middle column.) There are two possibilities for the two cells in the middle column: having the same color or having different colors. We note that $n=1$ is a special case where the only column is the middle column. This makes us to reckon that having different colors may lead to the right direction. Also, this vertical pair in the middle column is the only pair which does not have a mirroring pair in the whole grid. (Think again in a symmetric way.) If we want to have more pairs of different colors, it is wise to color this pair differently.
Meanwhile, the assumption of "guaranteeing the middle column to have different colors" hints that a possible strategy is always to pick the cell in the same column as the first mover does. This is also a simple but deterministic way for the late mover to pick up his cell in responding to his opponent's choice.
Now, we can follow the following guidelines to study the case when $n=3$:
- The two cells in the middle column have different colors.
- The late mover will always pick the cell in the same column as his opponent does.
We can also try to adopt an additional guideline by making the two columns with respect to the middle have the same pattern, i.e. either both have the same color or both have different colors.
This will leave just a handful of different situations to investigate. Upon completing this investigation, the above described winning strategy will become apparent.
$\textbf{Note}$
Here is the proof that adopting the described strategy will result in exactly one more pair of different colors.
Given $n$ is odd, there will be exactly one more odd-numbered column than even-numbered columns. As a result, there will be exactly one more different-colored vertical pair than same-colored vertical pairs. Hence, it is sufficient to show that there are equal number of different-colored and same-colored horizontal pairs in order to prove our claim. To show this, taking any $2\times 2$ grid, one of the two horizontal pairs must have the same color and the other has different colors by our described strategy. Therefore, the claim holds.