Question

. На большом листе клетчатой бумаги 20 клеток окрашены в чёрный цвет, остальные белые. Каждую секунду происходит перекрашивание клеток, при этом каждая клетка приобретает цвет большинства из трёх клеток: её самой и двух её соседей сверху и справа (скажем, если сейчас клетка белая, а два её соседа чёрные, то на следующем шаге она будет чёрной). Докажите, что через некоторое время все клетки станут белыми.

Answer 1

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

Answer 2

Задача: Перекрашивание клеток на листе бумаги

Мы имеем большой лист клетчатой бумаги, на котором 20 клеток окрашены в черный цвет, а остальные клетки белые. Каждую секунду происходит перекрашивание клеток в соответствии с правилом: каждая клетка принимает цвет большинства из трех клеток - самой клетки и двух ее соседей сверху и справа. Необходимо доказать, что через некоторое время все клетки станут белыми.

Решение:

Для доказательства этого утверждения, рассмотрим следующие факты:

1. В начальный момент времени у нас есть 20 черных клеток и остальные клетки белые. 2. При каждом шаге перекрашивания клетки, каждая клетка принимает цвет большинства из трех клеток - самой клетки и двух ее соседей сверху и справа. 3. Если клетка окружена только белыми клетками, то она останется белой на следующем шаге. 4. Если клетка окружена черными клетками, то она станет черной на следующем шаге.

Из этих фактов можно сделать следующие наблюдения:

- Если клетка окружена только белыми клетками, то она останется белой на следующем шаге. - Если клетка окружена черными клетками, то она станет черной на следующем шаге. - Количество черных клеток на листе бумаги не может увеличиваться, так как каждая черная клетка должна быть окружена хотя бы одной другой черной клеткой.

Таким образом, через некоторое время все клетки станут белыми, так как количество черных клеток будет уменьшаться на каждом шаге перекрашивания, и ни одна клетка не может стать черной, если она окружена только белыми клетками.

Доказательство:

1. В начальный момент времени у нас есть 20 черных клеток и остальные клетки белые. 2. При каждом шаге перекрашивания клетки, каждая клетка принимает цвет большинства из трех клеток - самой клетки и двух ее соседей сверху и справа. 3. Если клетка окружена только белыми клетками, то она останется белой на следующем шаге. 4. Если клетка окружена черными клетками, то она станет черной на следующем шаге. 5. Количество черных клеток на листе бумаги не может увеличиваться, так как каждая черная клетка должна быть окружена хотя бы одной другой черной клеткой.

Исходя из этих фактов, можно сделать вывод, что через некоторое время все клетки станут белыми.

Пример доказательства:

Предположим, что через некоторое время на листе бумаги осталась хотя бы одна черная клетка. Это означ