Can We Use Parity?

Consider an 8 × 8 8 \times 8 grid of squares. We color every square blue or green such that 3 of the 4 squares on the corners of the grid are blue and the fourth is green.

Will there always exist a 2 × 2 2 \times 2 square inside this grid such that there are an odd number of squares of each color inside?

Bonus: Generalize this for the n × n n \times n grid.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Geoff Pilling
Oct 29, 2016

What a great problem! (+1)

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

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

Consider the squares numbered as they are in this picture:

Now consider the 2 × 2 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 × 2 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 × 10 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 × 2 2\times2 grids of even parity, so, yes \boxed{\text{yes}} we can always find an odd parity 2 × 2 2\times2 grid in there somewhere! :0)

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

Great solution! +1

Sharky Kesa - 4 years, 7 months ago

Log in to reply

Hey thanks, @Sharky Kesa !

Geoff Pilling - 4 years, 7 months ago

That's very methodical. I was trying to do something like that, but kept getting confused about what to do next.

Chung Kevin - 4 years, 7 months ago
Calvin Lin Staff
Oct 29, 2016

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

Proof by contradiction. Suppose that there exists a configuration such that 2 × 2 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 × 2 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 × 2 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.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...