## Task A-2.5.

Ana covered a board of dimensions $2020 \times 2020$ with domino tiles that do not overlap, and each tile covers exactly two squares of the board. Branka wants to color these tiles such that for each tile, among its adjacent tiles, at most one is of the same color. Two tiles are adjacent if they cover squares that share a common side.

How many colors are needed at a minimum for Branka to be able to color the tiles in this way, regardless of how Ana arranged them?
## Solution.

We will prove that Branka has enough with three colors.

First, we will prove that Branka does not have enough with two colors (and thus not with fewer). We will find an example of Ana's tiling in which Branka cannot color the tiles with two colors.

![](https://cdn.mathpix.com/cropped/2024_05_30_87b35a0a71d93fe1a345g-09.jpg?height=623&width=625&top_left_y=888&top_left_x=721)

Suppose Ana tiles the upper left $3 \times 4$ part of the board as shown in the figure, and the remaining part by placing the tiles horizontally. Let's name the tiles as in the figure. Tiles $A, B$, and $C$ are all pairwise adjacent. Since we have two colors (1 and 2), by the Pigeonhole Principle, at least two of these tiles must be the same color (without loss of generality, color 1). If these are tiles $A$ and $B$, then all tiles adjacent to them must be color 2. That is, tiles $C, E$, and $F$ are colored 2, which means that $C$ has two adjacent tiles of the same color.

On the other hand, if $C$ is the same color as one of the tiles $A$ or $B$, then all other adjacent tiles to $C$ must be color 2. Then $D, E$, and $F$ are colored 2, which means that $D$ has two adjacent tiles of the same color.

In both cases, we arrive at a contradiction, so at least three colors are needed.

Now let's prove that, regardless of how Ana places the tiles, Branka can color the tiles with three colors in a valid way. Consider all the black squares of the $2020 \times 2020$ board if we were to color it black and white like a chessboard. Each tile, regardless of how Ana places it, will cover exactly one black square. Therefore, instead of coloring the tiles, it is enough to assign one of the three colors to each black square of the $2020 \times 2020$ board. We will color a tile with the color assigned to the black square it covers.

Additionally, for the construction of the coloring, divide the $2020 \times 2020$ board into $2 \times 2$ blocks. Coloring a block means assigning the same color to its black squares (i.e., the squares in the upper left and lower right corners). We color the blocks by alternating all three colors in sequence, as shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_30_87b35a0a71d93fe1a345g-10.jpg?height=825&width=828&top_left_y=176&top_left_x=614)

Two tiles can be adjacent only if the distance between the black squares they cover is at most 2. Therefore, consider two squares in the same $2 \times 2$ block to which the same color is assigned (without loss of generality, color 1). From the figure, we see that the squares to which color 1 is assigned have at most one square of the same color in their vicinity. Since this holds for any square with an arbitrarily assigned color, we conclude that all tiles will be adjacent to at most one tile of the same color.

## NATIONAL MATHEMATICS COMPETITION

## 3rd grade - high school - A variant

## October 26, 2020.