Can We Use Parity?

What a great problem! (+1)

Lets assume you can paint the $n\times n$ grid so that every $2\times2$ grid has an even number of blue squares. And prove by contradiction that there must be at least one "odd parity" $2\times2$ grid.

And for now, lets assume $n=10$ , although you'll see pretty quickly that the same argument is valid for all $n > 1$ .

Consider the squares numbered as they are in this picture:

Now consider the $2\times2$ grid in the lower left corner (81,82,91,92). It must have an even number of blue squares. Now consider the $2\times2$ grid (71,72,81,82) which also must have an even number of blue squares (or even parity). From these two facts you can conclude that the four squares (71,72,91,92) also must have even parity. A similar argument implies that (61,62,91,92) has even parity, and this can be continued vertically until you see that (1,2,91,92) have even parity.

Now, continuing this argument horizontally, (1,3,91,93) must have even parity, as would (1,4,91,94). Continuing this argument to the boundaries of the $10\times 10$ grid, this would imply that (1,10,91,100) would necessarily have even parity.

However, since the corners have odd parity (1 is one color and 3 are another) then we have a contradiction.

Therefore, we can't cover the array with with $2\times2$ grids of even parity, so, $\boxed{\text{yes}}$ we can always find an odd parity $2\times2$ grid in there somewhere! :0)

Clearly, we didn't use the fact that we took $n=10$ anywhere in the argument, so this argument is valid for all $n>1$ .

This solution is exactly identical to Geoff, but just expressed slightly differently.

Proof by contradiction. Suppose that there exists a configuration such that $2 \times 2$ square has an even number of squares. Let the blue squares be labelled as 1, and the green squares be labelled as 0.
For each $2 \times 2$ square, we define the "blue sum" as the sum of these 4 numbers (which gives us the number of blue squares that are in that square). By assumption, this "blue sum" is even.
Now, consider the sum of all the "blue sum" across $2 \times 2$ squares. This is the sum of several even numbers, hence is even.

We can represent this sum pictorially, where each circle touches the 4 squares that it sums.

From the image, we see every square that is not in the corner will be counted an even number of times. Hence, their contribution will be even. The corner squares will only be counted once. Hence, the parity of the "sum of all blue sums" depends just on the sum of these corner squares taken exactly once. Since 3 of them are colored blue, hence the parity must be odd.

Thus, we have a contradiction.