Клетчатые задачи и комбинаторные подсчёты на СПБГУ

Будем говорить, что конь контролирует клетку доски, если он бьёт эту клетку или стоит на ней. Докажем вначале, что менее коней убрать не удастся. Нам достаточно проверить, что с каждой половины доски придётся снять не менее коней. Рассмотрим для определённости верхнюю половину и отметим на ней шесть коней так, как показано на рисунке:

(для удобства они выделены разным цветом). Назовём клетки, отмеченные на рисунке кружочком, кратными, а остальные клетки простыми. Разобьём рисунок на два квадрата и зафиксируем один из них. Стоящие в квадрате чёрные кони бьют ровно по три клетки. Поэтому необходимо совершить одно из трёх действий.

Убрать двух коней, стоящих на простых клетках, контролируемых чёрными клетками (ими могут быть и сами чёрные кони).

Убрать коня, стоящего на кратной клетке. В результате белый конь из этого квадрата будет бить ровно трёх других коней. Значит, придётся ещё убрать коня с простой клетки, контролируемой белым конём (возможно, самого белого коня).

Те же действия необходимо проделать и для другого квадрата. Таким образом, каждый квадрат определяет пару клеток в верхней половине доски, с которых нужно убрать коней. Эти пары не пересекаются, поскольку никакие два отмеченных коня из разных квадратов не контролируют общих клеток. Иными словами, действия с квадратами производятся независимо друг от друга. Поэтому с верхней половины доски придётся убрать не менее четырёх коней.

Приведём пример, показывающий, что коней достаточно. На рисунке отмечены кони, которых нужно снять с доски.