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

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

С другой стороны, в столбцах стоит по две ладьи, а в остальных не более одной, поэтому всего их не более

Следовательно, всего ладей не больше, чем

Покажем далее как разместить ладей. На доске можно разместить ладьи как показано на рисунке, а затем поставить таких квадратов по диагонали.