Задача 73750

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

Сложность: 7 Классы: 9,10,11

Условие

Автор: Тоом А.Л.

На бесконечном клетчатом листе белой бумаги n клеток закрашены в чёрный цвет. В моменты времени t = 1, 2, 3,... происходит одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка k приобретает тот цвет, который имело в предыдущий момент большинство из трёх клеток: самой клетки k и её соседей справа и сверху (если две или три из этих клеток были белыми, то k становится белой, если две или три из них были чёрными,— то чёрной).

а) Докажите, что через конечное время на листе не останется ни одной чёрной клетки.

б) Докажите, что чёрные клетки исчезнут не позже, чем в момент времени t = n.

Решение

Пусть Ч – какое-то множество черных клеток. Обозначим буквой Γ (от слова "голосование") оператор перекрашивания, т.е. через Γ( Ч) будем обозначать множество клеток, которые получатся из Ч , через Γ²( Ч) – множество Γ (Γ( Ч)) , в которое перейдет Ч за два шага, через Γ³( Ч) – за три шага и т.д. (см.рис.7; кстати, этот рисунок опровергает предположение, что общее количество клеток в Γ( Ч) всегда меньше, чем в Ч ).

Утверждение а) сразу следует из двух таких почти очевидных предложений.

(1) Если к множеству Ч добавить еще черных клеток, то к множеству Γ( Ч) тоже могут только добавиться черные клетки, но ни одна не пропадет. Используя знак ( A B означает, что множество A целиком содержится в B , в частности, может с ним совпадать), это можно записать так:

Ч Ч' Γ( Ч) Γ( Ч').

(2) Если Ч₀ – множество всех клеток внутри квадрата на клетчатой бумаге (со стороной N клеток), то через конечное число шагов от Ч₀ ничего не останется (рис.8); точнее, уже через (2N-1) шагов получится пустое множество черных клеток: Γ2N-1 ( Ч₀)= .

Ясно, что любое множество Ч можно заключить в достаточно большой квадрат Ч₀ ; согласно(2) этот черный квадрат Ч₀ за конечное число шагов "вымрет", а согласно(1) и множество Ч не может просуществовать дольше, чем Ч₀ . Тем самым задача а) решена.

Доказать б) значительно труднее.

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

Кстати говоря, то, что решение б) не может быть очень простым, показывает разнообразие примеров множеств из n клеток, вымирающих ровно за n шагов (рис.9).

Докажем утверждение б) индукцией по n – количеству клеток в начальном множестве Ч ; для n=1 оно очевидно.

Пусть уже доказано, что если в Ч меньше n клеток, то

Γ^n-1 ( Ч)=.

Рассмотрим теперь Ч , состоящее из n клеток. Заключим его в прямой угол x 0 , y 0 (оси координат Ox и Oy направим вправо и вверх по линиям сетки, сторона клетки равна 1 ) так, чтобы в полосе 0 x 1 лежала хоть одна черная клетка и в полосе 0 y 1 – тоже (рис.10).

Пусть Ч¹ – часть Ч , лежащая в полуплоскости x 1 . По предположению индукции, Γ^n-1 ( Ч')= . А клетки из 0 x 1 не оказывают никакого влияния на то, что происходит выше прямой x=1 . Следовательно, Γ^n-1 ( Ч) целиком лежит в полосе 0 x 1 (очевидно, что в полуплоскости x<0 черные клетки возникнуть не могут).

Точно так же доказывается, что Γ^n-1 ( Ч) содержится в полосе 0 y 1 . Отсюда следует, что Γ^n-1 ( Ч) может содержать максимум одну клетку: 0 x 1 , 0 y 1 и, значит, Γⁿ ( Ч)= .

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

журнал
Название	"Квант"
год
Год	1973
выпуск
Номер	7
Задача
Номер	М215