Track / Stage 6 / 391 of 400 #1391 of 2000

Problem 1391

National olympiad, first round

Combinatorics Difficulty 7.0 Find the answer jbmo_shortlist

Let $n$ be a positive integer. We are given a $3n \times 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 \times 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.

Your answer

Official solution

Let $n$ be a positive integer, and consider a $3n \times 3n$ board with unit squares colored such that every third diagonal starting with the top left square is black, and the rest of the board is white. We need to determine for which values of $n$ it is possible to transform all initially black squares to white and all initially white squares to black using a series of moves, where each move consists of selecting a $2 \times 2$ square and changing the color of each of its squares cyclically through white, orange, black.

### Observations

1. Board Size and Coloring Pattern:
The board is $3n \times 3n$ , and every third diagonal is black. Given this structure, the number of black squares in the entire grid is $3n$ , since every third diagonal contains $n$ black squares, and there are three such diagonals within any $3 \times 3$ subgrid across the board.

2. Move Description and Effect:
Each move allows us to select a $2 \times 2$ square and change its colors according to the problem's rule. This means the total parity (modulo 2 sum of colors, treating white as 0 and black as 1) for each $2 \times 2$ change remains invariant modulo 2.

3. Parity Consideration:
Initially, the total number of black squares is odd, since the number of black squares $3n$ is proportional to $n$ .
- **For $n = 3$ :** The total number of black squares is $9$ , which is odd.
- **For $n = 2$ :** The total number of black squares is $6$ , which is even. Therefore, a transformation leaving the black-to-white parity unchanged is possible.

Solution Analysis

- **Case $n = 2$ :**

When $n = 2$ , the $3n \times 3n$ grid becomes a $6 \times 6$ board, and the problem's condition allows for transformation because the number of black squares can become equal to the number of initially white squares after applying the moves (switching colors maintains the condition).

- **Case $n = 3$ :**

When $n = 3$ , the number of black squares is odd (9). In this case, since moves only allow flipping an even 2x2 section of the board, there is no possible sequence of moves that solves the problem because the parity can't be balanced between black and white.

Hence, the values of $n$ for which the transformation is possible are:
$\boxed{n = 2}$

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.