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