lederhosen: (Default)
[personal profile] lederhosen
The problem I posted a couple of days ago:

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.

Profile

lederhosen: (Default)
lederhosen

April 2017

S M T W T F S
      1
2345 678
9101112131415
16171819202122
23242526272829
30      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 27th, 2017 07:17 pm
Powered by Dreamwidth Studios