For odd integers $n,$ two people play the game on $2\times n$ grid. Each people color one cell that is not colored before with white and black. When coloring is done, they count the number of ordered pairs of neighboring cells that have the same color and different color, respectively. If same color neighboring ordered pair of cells are more than different color neighboring ordered pair of cells, the person who first starts win and lose otherwise. (If the number is same, they are tied.) If both of them use the best strategy, find the result of the game.
Problem
Source: 2018 Korea Winter Program Practice Test #2
Tags: combinatorics
mathwiz_aku
01.02.2018 07:27
Define making a row "different" as coloring in the remaining square in the row with the opposite color of the square already colored in that row and making a row "similar" as coloring in the remaining square in the row with the same color of the square already colored in that row.
WLOG let Player 1 be the person that goes first, and Player 2 be the other person. I claim that Player 2 will win if he:
1. makes all odd-numbered rows different
2. makes all even-numbered rows similar
Consider the grid where all odd-numbered rows are different and all even-numbered rows are similar. Player 2 would win in this case and he can easily force Player 1 into this position because whenever Player 1 colors a square on a empty row, he can color the other square in the row and thus has the unique ability of making rows either different or similar. $\blacksquare$
Math1Zzang
25.02.2019 15:59
Suppose the person who starts the game is A, and the person who starts next is B. The game will become a tie for $n=2$ and B will win for $n\geq 3$.
We can see that the game will become a tie for $n=2$ quite easily.
Now suppose $n\geq 3$.
[asy][asy] for (int i=0 ; i<=2 ; ++i) {draw((0,i)--(3,i), grey);}
for (int i=0 ; i<=3 ; ++i) {draw((i,0)--(i,2),grey);}
pen border=black+2;
draw(box((0,0),(1,2)),border); draw(box((1,0),(3,1)),border); draw(box((1,1),(3,2)),border);
for (int i=0 ; i<=2 ; ++i) {draw((4,i)--(5,i),grey);}
for (int i=4 ; i<=5 ; ++i) {draw((i,0)--(i,2),grey);}
draw(box((4,0),(5,2)),border);
[/asy][/asy]
Denote the upper two shapes as $X$ and $Y$. Let $k=\left[\frac{n}{3}\right]$.
Divide the $2\times n$ grid into $k$ of the $X$ shapes and $n-3k$ of the $Y$ shapes.
So the $2\times n$ grid is now divided into $n$ dominos, and $B$ can play so that every domino has two cells of different color.
Let's count the number of pairs of neighboring cells of different color. There are $n$ such pairs inside the dominos.
Now denote the set of points that are included in the edges of both vertical dominos and horizontal dominos as $V$.
For every point $v$ in $V$, there is an additional pair of neighboring cells of different color,
other than that inside of the vertical domino.
Since $\left|V\right|=2k-1$ for $n=3k$, and $\left|V\right|=2k$ otherwise, the number of pairs of neighboring cells of different colors are
at least $5k-1$,$5k+1$,$5k+2$ for $n=3k$, $n=3k+1$, $n=3k+2$ respectively.
Recall that the total number of pairs of neighboring cells are $3n-2$.
So we can now see that more than half of the pairs of neighboring cells are pairs of neighboring cells of different color, and so $B$ wins.