Let n be a positive integer. We are given a 3n×3n board whose unit squares are colored in black and white in such way that starting with the top left square, every third diagonal is colored in black and the rest of the board is in white. In one move, one can take a 2×2 square and change the color of all its squares in such way that white squares become orange, orange ones become black and black ones become white. Find all n for which, using a finite number of moves, we can make all the squares which were initially black white, and all squares which were initially white black.
Proposed by Boris Stanković and Marko Dimitrić, Bosnia and Herzegovina
Let n be a positive integer. We are given a 3n×3n board whose unit squares are colored in black and white in such way that starting with the top left square, every third diagonal is colored in black and the rest of the board is in white. In one move, one can take a 2×2 square and change the color of all its squares in such way that white squares become orange, orange ones become black and black ones become white. The goals is, using a finite number of moves, we can make all the squares which were initially black white, and all squares which were initially white black. Prove that:
a) We cannot achieve the goal for n=3.
a) We can achieve the goal for n=2.
I claim that the answer is all even n.
Case 1: For even n, we just prove that is possible to switch everything for n=2 (trial and error) and now for all even n≥4, the picture is just made of many 6×6 squares, and switching each of these via the method for n=2 will guarantee that by the end all the colours will be flipped. This can be done by induction.
Case 2: Odd n
We will prove that if n is odd, we can never arrange the first row. We number each box with the number of moves required on it to make it to the colour it's supposed to be, so the white squares will be numbered 2, and the black squares 1. This will give us a sequence of 221221221221... with 6k+3 terms (it ends in a one).
This sequence will have its colours flipped if all its terms will be 0 (mod 3). Notice if we change the colour of a 2×2 square we will get two adjacent terms from the above sequence and decrease them both by one (we get them one step closer to completion). Now notice if we take the sum S=2−2+1−2+2−1+2−2+1... for all the terms in this sequence, the sum will be one.
Also notice that if we decrease two adjacent terms by one, it will not change S, therefore no matter how many moves you make, so we can never have all the terms to be 0 (mod 3) because S=1 (mod 3).
So no odd n will work.
Please tell me if there is a mistake in this solution.
I claim that the answer is all even n.
Case 1: For even n, we just prove that is possible to switch everything for n=2 (trial and error) and now for all even n≥4, the picture is just made of many 6×6 squares, and switching each of these via the method for n=2 will guarantee that by the end all the colours will be flipped. This can be done by induction.
Case 2: Odd n
We will prove that if n is odd, we can never arrange the first row. We number each box with the number of moves required on it to make it to the colour it's supposed to be, so the white squares will be numbered 2, and the black squares 1. This will give us a sequence of 221221221221... with 6k+3 terms (it ends in a one).
This sequence will have its colours flipped if all its terms will be 0 (mod 3). Notice if we change the colour of a 2×2 square we will get two adjacent terms from the above sequence and decrease them both by one (we get them one step closer to completion). Now notice if we take the sum S=2−2+1−2+2−1+2−2+1... for all the terms in this sequence, the sum will be one.
Also notice that if we decrease two adjacent terms by one, it will not change S, therefore no matter how many moves you make, so we can never have all the terms to be 0 (mod 3) because S=1 (mod 3).
So no odd n will work.
Please tell me if there is a mistake in this solution.
Wow, that's an amazing solution. You only need to provide a configuration for the 6×6 but defining S was a very clever way.
