Оценка:
Рассмотрим любой квадрат 2 на 2 клетки. Все его клетки покрашены в попарно различные цвета, так как иначе две клетки одного цвета стоят рядом. Значит, потребуется не менее четырёх цветов.
Пример:
Раскрасим таблицу вертикальными полосами в чёрный и белый цвета. Теперь пронумеруем все строки сверху вниз от 1 до 28. В каждой чётной строке перекрасим все белые клетки в светло-серые, а все чёрные - в тёмно-серые. Теперь для любой клетки две соседние с ней по строке клетки окрашены в другой цвет из-за изначальной раскраски полосами, а остальные - из-за замены цветов.
ответ: в 4 цвета.
