[ Chessboards and chess pieces $]$ [ Examples and counterexamples. Constructions ] [ Evenness and oddness

Authors: Pechkovsky A.N., Itenberg I.

Given an infinite grid paper with a cell side equal to one. The distance between two cells is defined as the length of the shortest path of a rook from one cell to another (the path of the center of the rook is considered). What is the minimum number of colors needed to color the board (each cell is colored with one color) so that two cells, located at a distance of 6, are always colored differently?

#
An example of coloring a square grid in four colors, such that any two cells at a distance of 6 are colored differently, is shown in the figure on the left.
![](https://cdn.mathpix.com/cropped/2024_05_06_579637707648b9944b26g-22.jpg?height=716&width=1874&top_left_y=1434&top_left_x=90)

Another example. Introduce a coordinate system on the square grid. It is sufficient to color the cells with even coordinate sums (the coloring of the remaining cells can be obtained from this by shifting 1 to the right). Points with coordinate sums divisible by 4 will be colored in two colors: if both coordinates are even - blue, if both are odd - red. Points with even but not divisible by 4 coordinate sums will be similarly colored in the remaining two colors. To prove that fewer colors cannot suffice, it is enough to consider the four cells shown in the figure on the right. Any two of them are located at a distance of 6 from each other, and therefore, all of them must be colored differently.

## Answer

In 4 colors.