Комбинаторика на БИБНе

Рассмотрим в нашем квадрате квадратов

Назовём их выделенными.

Заметим, что если одна клетка некоторого диполя принадлежит какому-то выделенному квадрату, то другая клетка этого диполя принадлежит (соседнему) выделенному квадрату.

На рисунке отмечены номерами клетки в выделенных квадратах, так что у любого диполя обе клетки должны иметь один и тот же номер. Но клеток с данным номером (например, с номером ) девять, и поэтому при “распределении” клеток с номером по диполям по меньшей мере одна клетка окажется нераспределённой (лишней). Таким образом, для каждого из четырех номеров остаётся нераспределённой минимум одна клетка среди выделенных квадратов, а значит, всего имеется минимум нераспределенные клетки.

Получаем оценку: максимальное число непересекающихся диполей во всём квадрате не больше

Построим теперь пример на диполей. Для этого “отрежем” левый нижний выделенный квадрат. Останется клетчатая фигура из клеток, которая разбивается на квадрат и два прямоугольника и Эта фигура полностью разбивается на диполи, поскольку любые последовательные клеток строки или столбца, очевидно, разбиваются на три диполя.