Задание:
. На большом листе клетчатой бумаги 20 клеток окрашены в черный цвет, остальные белые. Каждую секунду происходит перекрашивание клеток, при этом каждаяклетка приобретает цвет большинства из трех клеток: ее самой и двух ее соседей сверху и справа (скажем, если сейчас клетка белая, а два ее соседа черные, то на следующем шаге она будет черной). Докажите, что через некоторое время все клетки станут белыми.
Решение:
Рассмотрим прямоугольник, содержащий самую правую, самую левую, самую нижнюю и самую верхнюю клетки. Нам не важно, сколько в нем клеток, и сколько из них белых. Нам важно только то, что за его пределами черных клеток нет. Значит, если весь прямоугольник станет белым, то и все клетки станут белыми. Пусть верхняя правая клетка прямоугольника имеет координаты (0,0), а нижняя левая (-a,-b). После первой секунды клетка (0,0) точно будет белой (возможно, она была белой и раньше). После второй секуны станут белыми клетки (-1,0) , (0,-1), т.е. стоящие на следующей диагонали, так как их верхние и правые соседи точно белые. После третьей секунды станут белыми клетки следующей за ней диагональю, так как уже их верхние и правые соседи точно белые. В силу конечности размеров прямоугольника, он весь когда-нибудь станет белым, тогда и весь лист станет белым.
Знаете другой ответ?