Решение задачи 355

Условие:

Восемь клеток доски 9×9 заросли можжевельником. Далее, если вокруг пустой клетки не меньше двух клеток, заросших можжевельником (по стороне), то она зарастает можжевельником. Докажите, что вся доска не зарастет можжевельником.

Решение:

Периметром заросших клеток назовем количество сторон маленьких квадратиков, у которых ровно с одной стороны находится клетка, заросшая можжевельником. Например, на картинке (квадрат 6×6, фиолетовые клетки -- можжевельник) периметр заросших клеток равен 36.

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