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

Во-первых, докажем что Для этого полезно доказать более сильное утверждение: для произвольной фигуры из клеток количество квадратов в семействе, таком что все квадраты лежат в фигуре и для любого квадрата найдется клетка, покрытая только им, не превосходит Рассмотрим два случая: для семейства найдется клетка покрытая четырьмя квадратами, и случай, когда такой клетки не найдется.

Если такая клетка нашлась, то рассмотрим четыре покрывающих ее квадрата. Они образуют квадрат с клеткой в центре. И поскольку в каждом из четырех квадратов должна быть клетка, покрытая только им — это четыре угловые клетки квадрата поскольку все остальные покрыты хотя бы дважды. Но тогда никакой другой квадрат из семейства не покрывает клетки квадрат иначе он покрывает и угловую клетку, а она должна быть покрыта только один раз. Итак, все остальные квадраты лежат в множестве площади В этот момент доказательства еще не поздно решить, что на самом-то деле мы ведем индукцию по :), благо база тривиальна. Итак, всего квадратов в семействе оказывается не больше

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

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

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