Competition problem — Combinatorics

Library / /151 of 520

Combinatorics Difficulty 6.6 National olympiad Find the answer

Consider a board of $a \times b$ , with $a$ and $b$ integers greater than or equal to $2$ . Initially their squares are colored black and white like a chess board. The permitted operation consists of choosing two squares with a common side and recoloring them as follows: a white square becomes black; a black box turns green; a green box turns white. Determine for which values of $a$ and $b$ it is possible, by a succession of allowed operations, to make all the squares that were initially white end black and all the squares that were initially black end white.

Clarification: Initially there are no green squares, but they appear after the first operation.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

**
- For $a$ and $b$ both even, we can tile the board using $2 \times 3$ rectangles. Each $2 \times 3$ rectangle can be transformed to invert the colors.
- For $a$ even and $b$ odd (or vice versa), one side must be a multiple of 3. We can use $2 \times 3$ rectangles to cover the board and achieve the desired transformation.
- For $a$ and $b$ both odd, the number of black squares and white squares cannot be equal modulo 3, making the transformation impossible.

5. Conclusion:
The necessary and sufficient condition for the transformation to be possible is that $6$ divides $ab$ . This ensures that the board can be tiled with $2 \times 3$ rectangles, allowing the transformation.

$\boxed{6 \mid ab}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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