The cells of an $8 \times 8$ table are initially white. Alice and Bob play a game. First Alice paints $n$ of the fields in red. Then Bob chooses 4 rows and 4 columns from the table and paints all fields in them in black. Alice wins if there is at least one red field left. Find the least value of $n$ such that Alice can win the game no matter how Bob plays.
We will show that the least value of \( n \) is \( n=13 \).

If \( n \leq 12 \), Bob wins by painting black the 4 rows containing the highest numbers of red cells. Indeed, if at least 5 red cells remain, then one of the rows not blackened contains at least 2 red cells. Thus, each one of the rows blackened contained at least 2 red cells, and then all blackened cells were at least 8. However, in this case, at most 4 would be not blackened, a contradiction. It follows that at most 4 red cells remain which can be easily blackened by Bob choosing the 4 columns that they are in.

Now let \( n=13 \). Enumerate the rows and the columns from 1 to 8 and each field will be referred to by the pair (row, column) it is in. Let Alice paint in red the fields

\[
(1,1),(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(5,5),(6,6),(7,7),(8,8)
\]

as in the following figure.

![](https://cdn.mathpix.com/cropped/2024_06_05_cf1f7564beb0b6238161g-14.jpg?height=677&width=682&top_left_y=1049&top_left_x=687)

Suppose that Bob has managed to paint all red fields in black. The cells \((6,6),(7,7),(8,8)\) are painted black by three different lines (rows or columns) containing no other red fields, so the remaining 10 red fields have to be painted black by the remaining 5 lines. As no line contains more than 2 red fields, each red field has to be contained in exactly one of these lines. Assume that \((1,1)\) is painted black by a row, that is, row 1 is painted black. Let \( k \) be the least positive integer such that row \( k \) has not been painted black, where \( 2 \leq k \leq 5 \). Then field \((k, k-1)\) should be painted black by column \( k-1 \). However, in this column there is another red field \((j, k-1)\) contained in the painted row with number \( j < k \), which is a contradiction. Similar reasoning works if \((1,1)\) is painted black by a column.

Comment by PSC. Here is another reasoning to conclude that if Alice paints the table as above, then she wins.

Let \( A \) be the \( 5 \times 5 \) square defined by the corners \((1,1)\) and \((5,5)\).

Case 1: If Bob chooses 3 rows to paint black the cells \((6,6),(7,7)\) and \((8,8)\) then he has to use 1 row and 4 columns to paint in black the remaining 10 red squares in \( A \). Then no matter which 4 columns

Bob select, the remaining 1 column in \( A \) contains two red squares which cannot be painted in black using only 1 row. Similar reasoning stands if Bob chooses 3 columns.

Case 2: If Bob chooses 2 rows and 1 column to paint black the cells \((6,6),(7,7)\) and \((8,8)\), then he has to use 3 columns and 2 rows to paint in black the remaining 10 red squares in \( A \). Then, no matter which 3 columns Bob select, the remaining 2 columns in \( A \) contain 4 red squares in 3 different rows which cannot be painted in black using only 2 rows. Similar reasoning stands if
Bob chooses 1 row and 2 columns.