Разбиение доски на части

Мы покажем, что (i) если то любая хорошая расстановка содержат пустой квадрат но (ii) если то существует хорошая расстановка, которая его не содержит.

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

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

Пронумеруем строки снизу вверх, а столбцы слева направо числами Каждое поле доски будем обозначать, как обычно, парой номеров его строки и столбца. Теперь расставим ладьи на всех полях вида где (на рисунке ниже показано расположение для ). Поскольку каждое число от 0 до имеет уникальное представление вида каждая строка и каждый столбец содержат ровно одну ладью.

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

или, расположив эти числа в порядке возрастания,

Легко проверить, что первое число в этом списке не превосходит (если то а первое число в списке — ), последнее не превышает а разница между любыми двумя последовательными числами не превышает Таким образом, один из последовательных столбцов, пересекающих содержит число, указанное выше, и ладья в этом столбце находится внутри что и требовалось. Конструкция для установлена.

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