Некоторые клетки (хотя бы одну) белого клетчатого квадратного поля закрасили в красный цвет. Оказалось, что у каждой красной клетки ровно две соседние по стороне клетки тоже красные. 1. Сколько существует различных раскрасок с минимально возможным количеством красных клеток, если размер поля 6×6 клеток? (Поворачивать и разворачивать исходное клетчатое поле нельзя.)

Рассмотрим клетки как вершины графа: две вершины соединены, если клетки соседствуют по стороне. Тогда каждая красная клетка должна иметь ровно двух красных соседей.

Красные клетки разбиваются на замкнутые контуры: у каждой клетки в таком контуре ровно два соседа из контура. Самый короткий возможный контур на квадратной сетке — граница блока 2×2, состоящая из 4 клеток. Значит, красных клеток не может быть меньше четырёх.

Каждый блок 2×2 даёт подходящую раскраску: все четыре клетки блока красные, остальные белые. Внутри блока у каждой красной клетки ровно два соседа по стороне. Контур из четырёх клеток может быть только границей такого блока.

Блок 2×2 можно расположить в 6×6 поле шестью способами по горизонтали и шестью по вертикали. Поскольку повороты и отражения поля не отождествляются, считаем все расположения отдельно: 6 × 6 = 36.

Ответ: минимально 4 красные клетки; таких раскрасок 36.