Процессы и алгоритмы

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

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

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