ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 105125
Темы:    [ Периодичность и непериодичность ]
[ Таблицы и турниры (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В клетчатом прямоугольнике m×n каждая клетка может быть либо живой, либо мёртвой. Каждую минуту одновременно все живые клетки умирают, а те мёртвые, у которых было нечётное число живых соседей (по стороне), оживают.
Укажите все пары  (m, n),  для которых найдётся такая начальная расстановка живых и мёртвых клеток, что жизнь в прямоугольнике будет существовать вечно (то есть в каждый момент времени хотя бы одна клетка будет живой)?


Решение

  Достаточно рассмотреть случай  m ≤ n.  Пусть для некоторого n в прямоугольнике 1×n существует вечно живая расстановка. Тогда такая расстановка существует и во всех прямоугольниках m×n: берём вечно живую расстановку 1×n и копируем её во все строки прямоугольника m×n. Действительно, у каждой клетки мёртвого столбца соседи сверху и снизу мертвы, поэтому количество её живых соседей равно количеству живых соседних столбцов, а значит, и количеству живых соседей у соответствующей клетки в прямоугольнике 1×n. Поскольку в нём всегда остаётся хотя бы одна живая клетка, то в построенной расстановке m×n всегда остаётся хотя бы один живой столбец.
  При  n = 2  и  n ≥ 4  вечно живые расстановки 1×n существуют: каждая из нижеперечисленных расстановок имеет период 2, то есть каждую вторую минуту возвращается в исходное состояние.

  Кроме того, есть расстановка (также периода 2) в прямоугольнике 3×3:
    ЖЖМ          ММЖ
    МММ   ↔   ЖМЖ
    МЖЖ          ЖММ
  Тем самым, во всех прямоугольниках, кроме 1×1 и 1×3, примеры вечно живых расстановок уже построены.

  Покажем, что в прямоугольниках 1×1 и 1×3 любая расстановка рано или поздно умрёт. Случай 1×1 очевиден. Для случая 1×3 можно считать (возможно, начиная отсчёт со второго шага), что первая клетка мертва. Тогда остаётся 3 варианта, в которых есть хотя бы одна живая клетка. Эволюция варианта МЖЖ включает в себя и МЖМ:   МЖЖ → ЖММ → МЖМ → ЖМЖ → МММ, а вариант ММЖ симметричен варианту ЖММ, который также входит в рассмотренный выше пример.


Ответ

При всех парах чисел  (m, n),  кроме пар  (1, 1),  (1, 3)  и  (3, 1).

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

олимпиада
Название Московская математическая олимпиада
год
Номер 65
Год 2002
вариант
Класс 8
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .