$200 \times 200$ square is colored in chess order. In one move we can take every $2 \times 3$ rectangle and change color of all its cells. Can we make all cells of square in same color ?
Problem
Source: St Petersburg Olympiad 2010, Grade 10, P7
Tags: combinatorics, geometry, rectangle, Chessboard, invariant
AlirezaOpmc
07.11.2017 10:19
RagvaloD wrote: $200 \times 200$ square is colored in chess order. In one move we can take every $2 \times 3$ rectangle and change color of all its cells. Can we make all cells of square in same color ? What does "change" mean? Do we reverse colors? B to W and W to B?
nmd27082001
07.11.2017 15:25
i think the answer is yes
DreamComeTrue
07.11.2017 17:58
AlirezaOpmc wrote: RagvaloD wrote: $200 \times 200$ square is colored in chess order. In one move we can take every $2 \times 3$ rectangle and change color of all its cells. Can we make all cells of square in same color ? What does "change" mean? Do we reverse colors? B to W and W to B? yes reverse,and i think the answer is no
sunfishho
07.11.2017 22:05
Obviously, the number of cells that are white/black (respectively) at the start is $20000$. Without loss of generality, let us try to make all cells white. However, there will always be $2 (mod 3)$ cells that are white, and $2 (mod 3)$ cells that are black, which violates the condition we are trying to satisfy. Therefore, it is impossible to make all the cells in the chessboard the same color. EDIT: INVALID, will fix.
RagvaloD
07.11.2017 22:41
sunfishho wrote: However, there will always be $2 (mod 3)$ cells that are white, Why?
sunfishho
07.11.2017 22:52
thepiercingarrow wrote: Starts that way and every move u swap 3 whites and 3 blacks. Unfortunately, RagvaloD has a point. I will fix my solution now...
sunfishho
18.11.2017 23:41
/bump? R.I.P.
sunfishho
15.01.2018 23:58
Rebumping... I couldn't fix my solution... (i know it's a triple post, but what can i do?) As to the post I just deleted, I realize I said something completely incorrect oops...
conker23
16.01.2018 00:47
Sorry, the follwing is wrong. I "forgot" (...) to consider parity of numbers of change (if we change a case twice, it has the same colour). Sorry for that :s
As I've understood the statement, we can't rotate the rectangle which change values right ?
The trap is the initial colouring which "prevent" us from colouring in another way... But still, we can try ! Let's colour that way :
ABCDEFABCDEFABCDEF
DEFABCDEFABCDEFABC
ABCDEFABCDEFABCDEF
DEFABCDEFABCDEFABC
(In the following, I consider $3 times 2$ rectangles instead of $2 times 3$ rectangles...)
Say the first A is white. We notice that every white cases are either A, E or C.
When we apply a change, we change the colour of exactly one type of case.
But it's easy to see that the number of C in overall is less than the number of A. Therefore, we can't return at the same time all C cases and all A cases.
If we can rotate the rectangle, it doesn't work... Do you think we can ?
conker23
18.01.2018 18:06
I have something which works this time... It's easier that what I excepted. WLOG, suppose all cases are white. We want to turn all these cases black. Colour the chess in 3 colors : ABCABCABC CABCABCAB BCABCABCA Note that a 2x3 rectangle, whether it's vertical or horizontal, covers exactly 2 cases A, 2 cases B and 2 cases C. We'd like that one of the number of cases A,B or C is odd. Indeed, if for instance A is odd, then the number of A cases turned black would always stay even, and then there would always stay a A case white. Thus, not all A cases will never be black and we would be done. But it's easy to see that the number of cases A, B and C don't all have the same parity. Indeed,we remove successively 3 adjacent cases. That way, we keep the difference of parity beetween the different colors, if there's any. But in the end, we have a $2 *2$ square. In such a square, there's twice the same colour and exactly one of the two others. So the numbers of cases A, B and C don't have the same parity, and then one must be odd which conclude the impossibility to turn all cases black.
Pathological
26.05.2019 03:51
I think this might be similar to what conker23 did, but I can't really tell.
Label the rows and columns from top to bottom and left to right respectively with $1, 2, \cdots, 200.$ WLOG assume that the top-left corner is white. Call a square $(x, y)$ with $x+y \equiv 2$ (mod $3$) tasty. Then, by looking at all the tasty squares, we know that there are initially an odd number of white squares among the tasty squares, so since we toggle exactly $2$ squares which are tasty every time, there are an odd number of tasty white squares in the end as well. Hence, as there are an odd number of tasty squares, if all squares on the board were to be the same color in the end, they'd have to be white. However, if we repeat this argument after doing a $90$ degree rotation of the board, we get that they all have to be black, contradiction.