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.
From:
Anonymous
OpenID
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org


 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

lederhosen: (Default)
lederhosen

July 2017

S M T W T F S
      1
2345678
9101112131415
16171819202122
2324252627 2829
3031     

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 23rd, 2017 08:06 am
Powered by Dreamwidth Studios