Разобьём доску на 16 квадратиков 2×2 и покрасим их в разные цвета. Докажем, что больше 16 цветов получить нельзя. Рассмотрим клетку любого цвета. Рядом с ней есть ещё две клетки того же цвета. Эти две клетки имеют только одну соседнюю клетку того же цвета (среди рассмотренных), поэтому есть ещё хотя бы одна клетка такого же цвета. Итак, каждого цвета не меньше четырёх клеток, а следовательно, цветов не больше 16.
