, 2011

Suppose that at most 2 squares are colored red in any $2 \times 2$ square. Then in any $9 \times 2$ block, there are at most 10 red squares. Moreover, if there are 10 red squares, then there must be 5 in each row. This can be seen as follows. There are $8 \times 2 \times 2$ blocks. Counting multiplicity, there are altogether 16 red squares. Each red square in the interior is counted twice while each red square at the edge is counted once. If there are 11 red squares, then there are at least 7 red squares in the interior. Thus the total count is at least $4+7 \times 2 = 18 > 16$, a contradiction. If there are exactly 10 red squares, then 4 of them must be at the edge and the red squares in each row are not next to each other and hence there are 5 in each row.

Now let the number of red squares in row $i$ be $r_i$. Then $r_i + r_{i+1} \le 10$, $1 \le i \le 8$. Suppose that some $r_i \le 5$ with $i$ odd. Then
$$(r_1 + r_2) + \dots + (r_{i-2} + r_{i-1}) + r_i + \dots + (r_8 + r_9) \le 4 \times 10 + 5 = 45$$
which leads to a contradiction. On the other hand, suppose that $r_1, r_3, r_5, r_7, r_9 \ge 6$.
Then the sum of any 2 consecutive $r_i$'s is $\le 9$. Again we get a contradiction as
$$(r_1 + r_2) + \cdots + (r_7 + r_8) + r_9 \le 4 \times 9 + 9 = 45.$$