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

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

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