any solutions?

1. We claim that the least value of $n$ should be greater than $12$. 1.1 Consider $n=12$. Suppose $a_i$ is the number of red fields in row $i$, $1 \leq i \leq 8$. So $\sum_{i=1}^{8} a_i=12$. Consider the sum of the largest $4$ elements of $\{a_i\}$, let it be $m$. (1) We claim $m \geq 8$. If not, suppose the largest $4$ rows be set $A$ and the other $4$ rows be set $B$. The sum of red fields number in $A$, that is $m$, is less than $8$; so there is at least one row in $A$ including at most only $1$ red field, or else $m \geq 8$ (Pigeonhole principle). However, the sum of red fields number in $B$, that is $12-m$, is greater than 4; so there is at least one row in $B$ including at least $2$ red fields (Pigeonhole principle again). So there would be at least one row in $A$, the red field number of which is less than one row in $B$. This leads to contradiction since $A$ includes the largest $4$ red field number rows! (2) Select those $4$ rows to cover, and thus there would be less than $12-8=4$ red fields left. Obviously we could use no more than $4$ columns to cover the left red fields. So $n=12$ could always be covered by $4$ rows and $4$ columns. 1.2 If $n<12$, then randomly paint some additional fields red to $n=12$ and due to 1.1, it could be covered by $4$ rows and $4$ columns. 2. A construction of $n=13$. Consider the matrix below, where $1$ is the red fields and $0$ is white fields. There are $5$ rows and $5$ columns that include $2$ red fields. It can not be covered by $4$ rows and $4$ columns. $$\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} $$So the least value of $n$ is $\boxed{13}$.

Very clear and intuitive. Solution: Call a row/column Axis. That means an axis represents both row and column. Call an Axis good if it contains at least 2 red fields. If $n\le 12$, then why PHP there are at most 4 good axis. In that case Bob uses the following algorithm: Choose the 4 good axis first and then the bad axis accordingly (If any bad axis contain a red field,he will color it row-wise or column-wise whatever option left). Therefore,$n\ge 13$. We claim that $n=13$ is an valid choice.It can be justified by @above's example Or the following one: Paint the diagonal with red. Then paint any five field of the other diagonal. Hence $n=13$

$n=13$ is possible: $$\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} $$ It's enough to show that $n=12$ isn't possible. The most optimal way for Alice to color the first eight is such that every row and every column contains at exactly one red cell (This certainly exists: Paint along the longest diagonal). Otherwise, it's enough for Bob to use $7$. For the same reason, Alice must paint the four cells left with red such that every row and column contains at most $2$ red cells. Bob can simply make the first four moves such as each move eliminates two red cells and the next four moves eliminates one red cells.

The answer is $13$. To show that $n \le 12$ is winning for Bob, note that Bob can simply take the four most populated rows; this removes at least $8$ red cells, and Bob can cover the rest. On the other hand, Alice wins when $n = 13$ using the following set of red cells: \[ \begin{array}{|cccccccc|} \hline {\color{red}\blacksquare} & . & . & . & {\color{red}\blacksquare} & . & . & . \\ {\color{red}\blacksquare} & {\color{red}\blacksquare} & . & . & . & . & . & . \\ . & {\color{red}\blacksquare} & {\color{red}\blacksquare} & . & . & . & . & . \\ . & . & {\color{red}\blacksquare} & {\color{red}\blacksquare} & . & . & . & . \\ . & . & . & {\color{red}\blacksquare} & {\color{red}\blacksquare} & . & . & . \\ . & . & . & . & . & {\color{red}\blacksquare} & . & . \\ . & . & . & . & . & . & {\color{red}\blacksquare} & . \\ . & . & . & . & . & . & . & {\color{red}\blacksquare} \\ \hline \end{array} \] Remark: [Motivation] In general, one inductive idea is to find a red cell which is in only one row, and a red cell which is in only one column. These can be used to try and inductive approach, unless the cells happen to coincide. However, it is also fatal to have more than four such super-isolated cells for Alice. This leads to the construction above with exactly three such cells.

The answer is $n=\boxed{13}$. For a construction, Alice can color the squares $(i, i)$ for $1 \leq i \leq 8$, $(i+1, i)$ for $1 \leq i \leq 4$, and $(1, 5)$. Notice that any one of the first five columns takes at least two rows picked among the first five rows by Bob to eliminate, while the top three columns take at least one row each. This means that Bob can eliminate at most three columns of black squares by picking four rows, from where it follows that he cannot take out all the black squares by taking out four more columns. On the other hand, if $n \leq 12$, Bob can just strike out all the columns that have at least two black squares in them, which is guaranteed to be at most $4$, and any other columns if they are all gone. This means the remaining four columns only have one black square in them each, so he is always able to take out those squares by picking rows.

We claim the answer is $13$. For $n=13$, the following construction works: \[ \begin{bmatrix} \ast & . & . & . & . & . & . & . \\ . & \ast & . & . & . & . & . & . \\ . & . & \ast & . & . & \ast & . & . \\ . & . & . & \ast & . & . & . & . \\ \ast & . & . & . & \ast & . & . & . \\ . & \ast & . & . & . & \ast & . & . \\ . & . & \ast & . & . & . & \ast & . \\ . & . & . & \ast & . & . & . & \ast \end{bmatrix} \] For $n\leq 12$, note that by taking out the rows with the most reds, Bob can switch at least $8$ reds to blacks. He can then finish by taking out the last $4$ with his columns. Thus, $13$ is minimal.

Solved with proxima1681. I'm just posting because this is first combinatorics problem with an asymptote diagram lol Solution: The answer is $n = 13$. It clearly works due to the following construction. [asy][asy] size(5cm); for (int i=0; i<8; ++i) { for (int j=0; j<8; ++j) { draw(shift(i,j)*unitsquare); draw(shift(i,j)*unitsquare); } } for (int k=0; k<8; ++k) { dot((k+0.5,k+0.5), red); } // no brain left to code, so we bash dot((0.5,7.5), red); dot((7.5,0.5), red); dot((6.5,1.5), red); dot((5.5,2.5), red); dot((4.5,3.5), red); [/asy][/asy] It is clear that for $n \le 8$, Bob will obviously win. For $9 \le n \le 12$, by the pigeon-hole principle there will exist at least one column/row with more than one red cell(at max $4$). The winning strategy for Bob is to colour all the rows/columns with at least $2$ red cells and then cover rest of them by suitably colouring the rows and columns. This concludes the solution. $\blacksquare$

SatisfiedMagma wrote: It clearly works due to the following construction. Bob can choose rows numbered 1, 5, 6, 8 and columns numbered 2, 5, 6, 7, coloring every red square black. Edit: It seems like all the examples in this thread except the very first one by yamamaya are wrong

If $n \leq 12$ Claim: we can delete $4$ (rows or columns) containing $8$ or more red squares. Proof: Assume the otherwise, then the group of the $4$ columns containing the most red, eliminates at most $7$, so there is at least $1$(row or column) that only eliminates at most $1$, and the other $4$(row or column) deletes at least $5$, so there must be a row or column among these other $4$ which has at least $2$, and this is a contradiction because we said that the other $4$ were the ones that eliminated more red squares. $\blacksquare$ So, using the claim, we can eliminate at least $8$ with $4$(rows or columns) and it is clear that with the remaining $4$ it is possible to delete with the other $4$(row or column). $\Rightarrow n \geq 13$

e61442289 wrote: $\Rightarrow n \geq 13$ Rows 2 5 6 7 Columns 1 4 7 8

Case bash based on the largest number of red cells in a row/column to get that 12 doesn't work. For 13, I got the same construction as Evan, but flipped about the main diagonal.