Условие
На квадратном поле 10*10 девять клеток 1*1 поросли бурьяном.
После этого бурьян может распространиться на клетку,
у которой не менее двух соседних клеток уже поросли бурьяном.
Докажите, что тем не менее бурьян не сможет распространиться на
все клетки.
Подсказка
Как изменяется периметр области, поросшей бурьяном?
Решение
Рассмотрим границу области, поросшей бурьяном (т.е.
все отрезки длиной 1 между узлами, по одну сторону от которых бурьян,
а по другую - нет).
Вначале длина границы была не более 9*4=36, поскольку бурьян рос
только в девяти клетках.
Нетрудно заметить, что в процессе распространения бурьяна
длина границы не может увеличиваться.
Но если бы все поле 10*10 в некоторый момент оказалось поросшим
бурьяном, то длина границы стала бы равной 10*4=40,
что противоречит соображениям, приведенным выше.
Источники и прецеденты использования
