В какое наибольшее число цветов можно раскрасить шахматную доску 8*8 так, чтобы каждая клетка граничила по стороне хотя бы с двумя клетками своего цвета? (Каждая клетка закрашивается целиком в один цвет.)

В 16 цветов точно можно

Рассмотрим квадратик, который в углу: рядом с ним 2 - красим в его же цвет, минимум надо еще 1, чтобы для этих 2 тоже условие выполнялось (получим квадратик 2 х2). покраска в один цвет закончена ...

на поле 8 х8 таких квадратиков 16

Ответ: максимум 16 цветов