There is a natural number n given and a table with 2n x 2n cells, which are all white. A and B play the following game. First A paints m of the cells in red. Then B chose n rows and n columns and paints the cells in them in black. A wins when there is at least one red cell left. Find the smallest possible value of m, for which A can win no matter how B plays.
This is an interesting problem from a Singaporean combinatorics and game theory textbook, but I don't know how to solve it.
Can you suggest a solution? Thank you in advance!
$m\leqslant 2n$ is not enough for A to win, because B can then choose the rows containing $n$ of A's red squares and the columns containing the rest of A's red squares.
$m=4n$ is enough: Denote the square where column $x$ crosses row $y$ by $(x, y)$, with $0\leqslant x, y<2n$. Let A choose $4n$ squares $P_0,\dots, P_{4n-1}$ with $P_{2i}=(i, i), P_{2i+1}=(i, i+1)$ except that $P_{4n-1}=(2n-1, 0)$. Interpret indices of $P$ modulo $4n$.
Use "line" to mean a row or a column. Then every line contains 2 red squares, so each line chosen by B blacks out at most 2 red squares not already blacked out. Thus the only way B can win is if each line they choose blacks out exactly 2 red squares not already blacked out, and does not black out any red square that is already blacked out. In each case these 2 red squares must be $P_j$, $P_{j+1}$ for some $j$.
In particular, B blacks $P_1$ by choosing either $x=0$, which also blacks $P_0$, or $y=1$, which also blacks $P_2$. In the former case, B can black $P_2$ only together with $P_3$, by choosing $x=1$; in the latter case, B can black $P_3$ only together with $P_4$, by choosing $y=2$. And so on. In each case, for B to black all $4n$ red squares they must choose $2n$ parallel lines. But the rules entail B choosing $n$ rows and $n$ columns. So in this case B cannot win, so A wins.