Подсчеты в клетчатых задачах

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

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

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