### Problem solution

Apr. 25th, 2011 10:42 am**lederhosen**

The problem I posted a couple of days ago:

Mark the squares of the board as follows:

12312312

23123123

31231231

12312312

23123123

31231231

12312312

23123123

Note that at the start there are 21 white '1's and 22 white '2's (along with 21 white '3's, but we don't need them for what follows). The total of (white '1's + white '2's) is 43.

Any 3x1 rectangle will contain exactly one of each mark. So any time we colour-flip a rectangle, the number of white '1's changes by ±1, and similarly for the '2's. So each colour-flip will change the total of (white '1's + white '2's) by 0 or ±2.

Since it starts out at 43, this means it can never be even, which means it can never be zero - therefore we will always have at least one white square.

This is what's known as a

An 8 by 8 square is painted white. We are allowed to choose any rectangle consisting of 3 of the 64 (1 by 1) squares and paint each of the 3 squares in the opposite colour (the white ones black, the black ones white). Is it possible to paint the entire square black by means of such operations?

Mark the squares of the board as follows:

12312312

23123123

31231231

12312312

23123123

31231231

12312312

23123123

Note that at the start there are 21 white '1's and 22 white '2's (along with 21 white '3's, but we don't need them for what follows). The total of (white '1's + white '2's) is 43.

Any 3x1 rectangle will contain exactly one of each mark. So any time we colour-flip a rectangle, the number of white '1's changes by ±1, and similarly for the '2's. So each colour-flip will change the total of (white '1's + white '2's) by 0 or ±2.

Since it starts out at 43, this means it can never be even, which means it can never be zero - therefore we will always have at least one white square.

This is what's known as a

*colouring proof*; I had the advantage of having run into the approach once before, although not for this particular problem.