Let $n$ and $k$ be given integers such that $n\ge k\ge 2$. Alice and Bob play a game on an $n$ by $n$ table with white cells. They take turns to pick a white cell and color it black. Alice moves first. The game ends as soon as there is at least one black cell in every $k$ by $k$ square after a player moves, who is declared the winner of the game. Who has the winning strategy?
Problem
Source: CWMI 2017 Q4
Tags: combinatorics
18.08.2017 11:02
[redacted] the previous answer is probably wrong
07.03.2018 06:13
Divide the problem into several cases: Case 1: When $k > 1/2n$: Alice immediately wins by coloring the middle square black if $n$ is odd, or by coloring one of the 4 middle squares if $n$ is even. Case 2a: When $k \leq 1/2 n$, and $n$ is odd: Alice wins. First, she colors the middle square black. From then onward, whenever Bob moves, Alice copies his move by coloring the square directly opposite (with respect to the center square) the square Bob just colored. By symmetry this is always possible. Claim: Bob cannot win. Proof: Consider a k by k subgrid to be empty if there are no black squares in it. Note that immediately after Alice's move, each empty $k$ by $k$ subgrid must have a corresponding empty $k$ by $k$ subgrid that is the opposite of it with respect to the center square. This is true since Alice always colors the square that is opposite Bob's. Claim: Within each pair of corresponding empty $k$ by $k$ subgrids, both of them are mutually disjoint. Proof: Suppose not. Then both of them necessarily contain the center black square, which is a contradiction of the emptiness of the two subgrids. Hence claim proven. Hence, immediately after Alice moves (after Bob moves), the number of empty $k$ by $k$ subgrids must be in pairs of 2, which makes the sum even. Observe that since within each pair Bob can make at most one of them non-empty, so Bob cannot win. Since the game must terminate, Alice wins. Case 2b: When $k \leq 1/2 n$, and $n$ is even: Bob wins. After each of Alice's moves, Bob checks if there exists two mutually disjoint empty $k$ by $k$ subgrids. (They need not necessarily be directly opposite other and they do not need to be fixed). If there exists, then Bob colors a square that is outside both mutually disjoint empty $k$ by $k$ subgrids. This is always possible due to parity, since Alice has colored one more square than Bob at that point in time, implying that there is an odd (and therefore $>0$) number of white squares outside the aforementioned subgrids. After some series of moves and upon Bob's turn, when Bob checks and finds that there do not exist two mutually disjoint empty $k$ by $k$ subgrids, it necessarily implies that Alice, in her last move, colored a square within one of the two mutually disjoint empty $k$ by $k$ subgrids. Now any two empty $k$ by $k$ subgrids must overlap, if there is more than one empty $k$ by $k$ subgrid. This means that all the empty $k$ by $k$ subgrids must overlap together on at least one square (since they are pairwise non-disjoint). Bob colors one of the squares black, and wins.
03.06.2018 09:41
Just curious, is the one who puts the last black square the winner or the loser?