Question

Есть лист клетчатой бумаги и карандаши 6 цветов. Закрасьте наименьшее число клеток так, чтобы для любых двух цветов нашлись две клетки этих цветов, граничащие по стороне. Докажите, что меньшее число клеток закрасить нельзя.

Answer 1

Меньше 12 закрасить не получится: на клетчатой бумаге у каждой клетки по 4 соседа, а для выполнения условия задачи нужно не меньше 5 соседей с клетками одного цвета. Ровно 12 можно: см. рисунок.