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

Пример для доски изображен на картинке и естественным образом обобщается на любое нечетное число.

Первое решение.

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

поскольку суммарное количество длин всех ребер равно количеству клеток доски.

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

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

с другой,

поскольку каждому ребру первого типа соответствует ровно один, а каждому ребру второго типа соответствует ровно два уникальных квадрата, общее количество которых равно .

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

Наконец,

следовательно,

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

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