TOT 057 1984 Spring J-O5 J-A1 coloring an infinite squared sheet
Source:
August 19, 2019
Coloringminimumtableinfinite boardcombinatorics
Problem Statement
An infinite squared sheet is given, with squares of side length . The “distance” between two squares is defined as the length of the shortest path from one of these squares to the other if moving between them like a chess rook (measured along the trajectory of the centre of the rook). Determine the minimum number of colours with which it is possible to colour the sheet (each square being given a single colour) in such a way that each pair of squares with distance between them equal to units is given different colours. Give an example of such a colouring and prove that using a smaller number of colours we cannot achieve this goal.(AG Pechkovskiy, IV Itenberg)