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

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