## Task A-1.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 neighboring tiles, at most two are of the same color. Two tiles are neighbors if they cover squares that share a 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 two colors.

It is obvious that Branka cannot color all the tiles with one color: every tile that is not on the edge has at least four neighboring tiles (which touch it from below, above, left, and right) and which are the same color as the observed one, which is not allowed.

Now let's prove that, regardless of how Ana places the tiles, Branka can color the tiles with two colors in a correct way. Consider all the black fields of a $2020 \times 2020$ board when we would color it black and white like a chessboard. Each tile, regardless of Ana's placement, will cover exactly one black field. Therefore, instead of tiles, it is enough to assign one of two colors to each black field of the $2020 \times 2020$ board. We will color the tile with the color assigned to the black field it covers.

We do this as shown in the figure: we assign the colors 1 and 2 alternately to the fields of the black diagonal. Consider any black field. Without loss of generality, we can assume that the color 1 is assigned to this field. The tile that covers this field will be adjacent to some of the eight black fields that are two fields away from this field. Among these fields, only two have the color 1 assigned to them. Since this is true for any field, we conclude that all tiles will be adjacent to at most two other tiles of the same color.

![](https://cdn.mathpix.com/cropped/2024_05_30_87b35a0a71d93fe1a345g-05.jpg?height=614&width=623&top_left_y=1583&top_left_x=725)

## NATIONAL MATHEMATICS COMPETITION

## 2nd grade - high school - A variant

## October 26, 2020.