Комбинаторика на Высшей пробе: клетки, комбигео, игры, графы

Для начала определим разбиение клетчатого прямоугольника

которое в дальнейшем будем называть спиральным. Нарисуем спираль, начиная двигаться из угла вдоль короткой стороны прямоугольника, если они не равны. Затем расположим в центре спирали квадратик за ним — прямоугольник а затем будем накрывать все непокрытые клетки частично покрытого отрезка спирали прямоугольником ширины 1 и соответствующей длины.

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

а ширину строки равной

где

Далее разобьем неравномерный клетчатый прямоугольник на

прямоугольников (назовем их ) по линиям сетки. Выясним, какие прямоугольники можно сложить из подмножества множества малых прямоугольников.

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

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

Тогда, если некоторый прямоугольник сложен из малых, все малые прямоугольники в нем ориентированы одинаково.

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение 1. Пусть даны некоторые целые неотрицательные числа, не превышающие

Тогда если

то для всех

Предположим, что для некоторых различных наборов и оказалось, что

Пусть — наибольшее число, при котором

Не умаляя общности положим, что Тогда

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение 2. Пусть даны некоторые целые неотрицательные числа, не превышающие

Тогда если

то для всех

Доказывается аналогично утверждению 1.

_________________________________________________________________________________________________________________________________________________________________________________

По построению для любого малых прямоугольников ширины не больше

а малых прямоугольников высоты не более

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

где — целые неотрицательные числа, не превышающие Аналогично, высота прямоугольника представима в виде

где — целые неотрицательные числа, не превышающие

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

Из утверждения 1 следует, что любая такая прямая пересекает ровно прямоугольников ширины Значит, из всех прямоугольников ширины можно сложить прямоугольников размера

Из утверждения 2 следует, что для каждого такого прямоугольника нам нужно использовать малых прямоугольников высоты Получается, для построения нашего прямоугольника нам понадобится не менее малых прямоугольников размера С другой стороны, все малые прямоугольники различны, а значит, все и равны либо 0, либо 1.

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

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

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

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

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

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

Получается, состоит из всех прямоугольников разбиения, что и требовалось.