Problem

Source: VI International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade

Tags: combinatorics, table, Coloring, covering



A cross with length $p$ (or p-cross for short) will be called the figure formed by a unit square and 4 rectangles $p-1$ x $1$ on its sides. What’s the least amount of colors one has to use to color the cells of an infinite table, so that each p-cross on it covers cells, no two of which are in the same color?