
Problem 2. All the squares of a $2024 \times 2024$ board are coloured white. In one move, Mohit can select one row or column whose every square is white, choose exactly 1000 squares in this row or column, and colour all of them red. Find the maximum number of squares that Mohit can colour red in a finite number of moves.


Solution. Let $n=2024$ and $k=1000$. We claim that the maximum number of squares that can be coloured in this way is $k(2 n-k)$, which evaluates to 3048000 .

Indeed, call a row/column bad if it has at least one red square. After the first move, there are exactly $k+1$ bad rows and columns: if a row was picked, then that row and the $k$ columns corresponding to the chosen squares are all bad. Any subsequent move increases the number of bad rows/columns by at least 1 . Since there are only $2 n$ rows and columns, we can make at most $2 n-(k+1)$ moves after the first one, and so at most $2 n-k$ moves can be made in total. Thus we can have at most $k(2 n-k)$ red squares.

To prove this is achievable, let's choose each of the $n$ columns in the first $n$ moves, and colour the top $k$ cells in these columns. Then, the bottom $n-k$ rows are still uncoloured, so we can make $n-k$ more moves, colouring $k(n+n-k)$ cells in total.
