Задача 79493

Темы:    [ Геометрия на клетчатой бумаге ] [ Полуинварианты ]

Сложность: 4+ Классы: 9,10

Условие

Квадратное поле разбито на 100 одинаковых участков, 9 из которых поросли бурьяном. Известно, что бурьян за год распространяется на те и только те участки, у каждого из которых не менее двух соседних участков уже поражены бурьяном (участки соседние, если они имеют общую сторону). Докажите, что полностью все поле бурьяном не зарастёт.

Решение

Легко проверить, что длина границы всего заросшего бурьяном участка (или нескольких участков) не возрастает. В начальный момент она не превосходит 9 ^. 4 = 36, поэтому в конечный момент она не может быть равной 40.

Источники и прецеденты использования

книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	23
Название	Делимость, инварианты, раскраски
Тема	Неопределено
параграф
Номер	3
Название	Инварианты
Тема	Инварианты
задача
Номер	23.016
олимпиада
Название	Московская математическая олимпиада
год
Номер	49
Год	1986
вариант
Класс	8
задача
Номер	4