1. [6] In an empty $100 \times 100$ grid, 300 cells are colored blue, 3 in each row and each column. Compute the largest positive integer $k$ such that you can always recolor $k$ of these blue cells red so that no contiguous $2 \times 2$ square has four red cells.
Answer: 250
Solution: We first prove the lower bound. We can recolor all three blue cells in odd rows, and the first and third blue cells in even rows.
A $2 \times 2$ square must cover two adjacent cells in an even row. Therefore, it's impossible for there to exist a red $2 \times 2$ square in our recoloring, because coloring the first and third cell in each even row guarantees that no two adjacent cells are both red in that row.
This colors $50 \times 3+50 \times 2=250$ cells.
For the upper bound, consider the configuration with 50 disjoint $2 \times 2$ squares colored blue along the diagonal. Then, color the remaining 100 cells more or less arbitrarily (for instance, the other main diagonal).
For each $2 \times 2$ blue square, we can color at most 3 of those cells red. Therefore, we can recolor at most $3 \cdot 50+100=250$ cells.