Олимпиадная задача: раскраска шахматной доски 8×8 в максимум цветов
В какое наибольшее количество цветов можно раскрасить клетки шахматной доски 8×8 так, чтобы каждая клетка граничила по стороне хотя бы с двумя клетками того же цвета?
Показать ответ
В 16 цветов.
Разобрать решение
Разделим доску на 16 квадратов 2×2 и каждый квадрат раскрасим своим цветом. Эта раскраска в 16 цветов удовлетворяет условию.
Большего количества цветов добиться не удастся. Действительно, если клеток какого-то цвета не более трёх, то только одна из них может граничить по стороне с двумя клетками своего цвета (см. рис.).
Если же клеток каждого цвета не менее четырёх, то различных цветов не более шестнадцати.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.