Задачи на логику, головоломки, загадки, ребусы - Л О Г О - Р А Й

Принцип Дирихле

В какое наибольшее число цветов можно раскрасить клетки доски 8×8 так, чтобы у каждой клетки среди её соседей (по стороне) были хотя бы две клетки, окрашенные в тот же цвет?

Ответ:

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