РЕШУ ОЛИМП — математика

Задания

В клетчатом квадрате $8 \times 8$ две клетки одной строки или столбца назовем диполем, если между ними ровно две клетки. Петя решил отметить как можно больше диполей, закрашивая разными цветами разные диполи (а обе клетки одного и того же диполя  — одним цветом). Какое наибольшее количество диполей он сможет закрасить?

Решение.

Рассмотрим в нашем квадрате 9 квадратов $2 \times 2$ (см. рис.), назовём их выделенными. Заметим, что если одна клетка некоторого диполя принадлежит какому-то выделенному квадрату, то другая клетка этого диполя принадлежит (соседнему) выделенному квадрату. На рисунке отмечены номерами 1, 2, 3, 4 клетки в выделенных квадратах, так что у любого диполя обе клетки должны иметь один и тот же номер. Но клеток с данным номером (например, с номером 1) девять, и поэтому при «распределении» клеток с номером 1 по диполям по меньшей мере одна клетка окажется нераспределённой (лишней). Таким образом, для каждого из четырех номеров остаётся нераспределённой минимум одна клетка среди выделенных квадратов, а значит, всего имеется минимум 4 нераспределенные клетки. Получаем оценку: максимальное число непересекающихся диполей во всём квадрате $8 \times 8$ не больше $дробь: числитель: 64 минус 4, знаменатель: 2 конец дроби =30.$ Построим теперь пример на 30 диполей. Для этого «отрежем» левый нижний выделенный квадрат. Останется клетчатая фигура из 60 клеток, которая разбивается на квадрат $6 \times 6$ и два прямоугольника $6 \times 2$ и $2 \times 6.$ Эта фигура полностью разбивается на диполи, поскольку любые последовательные 6 клеток строки или столбца, очевидно, разбиваются на три диполя.

Ответ: 30.

Ключ