Разделы 
Дополнительно
Задача по математике - 3703
2019-06-16 
На бесконечном клетчатом листе белой бумаги $n$ клеток закрашено в черный цвет. В моменты времени $t = 1, 2, \cdots$ происходит одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка $k$ приобретает тот цвет, который имело в предыдущий момент большинство из трех клеток: самой клетки $k$ и ее соседей справа и сверху (если две или три из этих клеток были белыми, то $k$ становится белой, если две или три из них были черными - то черной), а) Докажите, что через конечное время на листе не останется черных клеток; б) Докажите, что черные клетки исчезнут не позже чем в момент времени $t = n$.
Решение:
а) Заметим, что если к данному множеству черных клеток добавить еще несколько черных клеток, то после перекрашивания могут возникнуть лишь дополнительные черные клетки. Добавим к исходному множеству $M$ клетки так, чтобы получился черный квадрат $m \times m$ клеток.
Через $2m-1$ шагов от квадрата (а, значит, и от $M$) ничего не останется.
б) Будем множество черных клеток, которое получается из $M$ за $t$ шагов, обозначать через $M_t$. Докажем индукцией по $n$, что для любого множества $M$ из $n$ клеток $M_n$ пусто. (Для $n = 1$ это ясно.) Пусть для множеств менее чем из $n$ клеток это доказано, и рассмотрим произвольное множество $M$ из $n$ клеток. Мы можем считать, что $M$ лежит на координатной плоскости $Оxy$ в углу $x \geq 0, у \geq 0$, причем в полосах $0 \leq x \leq 1$ и лежит по крайней мере по одной клетке из $M$ (рис.). Тогда по предположению индукции $M_{n-1}$ не пересекается с углом $x \geq 0, у \geq 1$ (клетки в полосе $0 \leq x \leq 1$ не влияют на происходящее при следовательно, $M_{n-1}$ лежит в полосе $0 \leq x \leq 1$. Аналогично можно доказать, что $M_{n-1}$ лежит в полосе $0 \leq у \leq 1$. Значит, $M_{n-1}$ может содержать лишь одну клетку, а $M_n$ пусто.
На бесконечном клетчатом листе белой бумаги $n$ клеток закрашено в черный цвет. В моменты времени $t = 1, 2, \cdots$ происходит одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка $k$ приобретает тот цвет, который имело в предыдущий момент большинство из трех клеток: самой клетки $k$ и ее соседей справа и сверху (если две или три из этих клеток были белыми, то $k$ становится белой, если две или три из них были черными - то черной), а) Докажите, что через конечное время на листе не останется черных клеток; б) Докажите, что черные клетки исчезнут не позже чем в момент времени $t = n$.
Решение:
а) Заметим, что если к данному множеству черных клеток добавить еще несколько черных клеток, то после перекрашивания могут возникнуть лишь дополнительные черные клетки. Добавим к исходному множеству $M$ клетки так, чтобы получился черный квадрат $m \times m$ клеток.
Через $2m-1$ шагов от квадрата (а, значит, и от $M$) ничего не останется.
б) Будем множество черных клеток, которое получается из $M$ за $t$ шагов, обозначать через $M_t$. Докажем индукцией по $n$, что для любого множества $M$ из $n$ клеток $M_n$ пусто. (Для $n = 1$ это ясно.) Пусть для множеств менее чем из $n$ клеток это доказано, и рассмотрим произвольное множество $M$ из $n$ клеток. Мы можем считать, что $M$ лежит на координатной плоскости $Оxy$ в углу $x \geq 0, у \geq 0$, причем в полосах $0 \leq x \leq 1$ и лежит по крайней мере по одной клетке из $M$ (рис.). Тогда по предположению индукции $M_{n-1}$ не пересекается с углом $x \geq 0, у \geq 1$ (клетки в полосе $0 \leq x \leq 1$ не влияют на происходящее при следовательно, $M_{n-1}$ лежит в полосе $0 \leq x \leq 1$. Аналогично можно доказать, что $M_{n-1}$ лежит в полосе $0 \leq у \leq 1$. Значит, $M_{n-1}$ может содержать лишь одну клетку, а $M_n$ пусто.
