Конструктивы в алгебре

Утверждение. Функция высоты задаёт разбиение единственным образом.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Будем вести индукцию по величине .

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

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