Турнир LEDAS «Жизнь»

Компания ЛЕДАС приглашает математиков-программистов отметить полвека, прошедших со времени публикации статей об игре «Жизнь». В 1970 году математик Джон Конвей придумал изящные правила, а сейчас мы приглашаем вас эти правила обратить (т.е. найти предшествующее состояние по заданному). В таблицу рекордов ниже вы сможете внести своё имя и название своей организации. Для этого надо построить такую конфигурацию, из которой через несколько ходов получится конфигурация, похожая на надпись «LEDAS» (см. в нашем блоге LEDAS Life Contest).

Напомним коротко правила игры «Жизнь»: вселенная — это бесконечная квадратная решётка, в которой каждая клетка может быть лишь в одном из двух состояний: жива или мертва. Каждая клетка взаимодействует только со своими восемью соседями: по горизонтали, вертикали и диагонали.

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

Правила игры «Жизнь» очень просты, поэтому миллионы программистов уже реализовывали системы для построения следующего состояния по заданному. Но вот в прошлое идти не так просто (есть даже теорема о том, что невозможно за разумное время для произвольной конфигурации). Поэтому мы приглашаем вас поучаствовать в решении исследовательской математической задачи — найти именно предшествующее состояние к нашему целевому. В этом смысле, мы предлагаем «обратить правила» игры «Жизнь».

Цель соревнования

Надо построить минимальную конфигурацию, которая через несколько итераций станет как можно более похожей на целевую конфигурацию (надпись «LEDAS»).

За каждую живую клетку вашей начальной конфигурации придётся заплатить 3 очка, а за каждое отличие вашей финальной конфигурации от нашей целевой — 11 очков. Соответственно, надо набрать как можно меньше очков.

Сразу договоримся, что из двух конфигураций с равным количеством очков побеждает та, которой потребуется больше итераций (а из двух с равным количеством итераций та, которую вы нам раньше пришлёте).

Итак, начнём соревнование! Целевая конфигурация выглядит следующим образом:

Целевая конфигурация

Давайте посмотрим, что будет, если наша начальная конфигурация не содержит живых клеток. Легко понять, что она никогда не изменится, то есть совпадает с конфигурацией на любом шаге. Соответственно, здесь у нас всегда будет ровно 48 отличий от целевой конфигурации (ведь в целевой конфигурации ровно 48 живых клеток). Это стоит нам 48 * 11 = 528 очков.

Давайте попробуем улучшить эту первую попытку. Если мы начнём с конфигурации, изображённой ниже, то это будет нам стоить 27 * 3 = 81 очко, поскольку изначально у нас здесь 27 живых клеток, а каждая стоит 3 очка.

Начальная конфигурация стоит 81 очко

И на следующем шаге мы получим следующую конфигурацию:

Результат первой итерации

Давайте сравним этот результат с целью:

Отличия показаны красным

Это стоит нам 27 * 11 = 297 очков, потому что мы имеем 27 отличий от цели, а каждое отличие стоит 11 очков.

Выходит, эта вторая попытка оценивается в 81 + 297 = 378 очков, что заметно лучше 528 очков, полученных на пустом поле. Более того, эта конфигурация не хуже любой другой 378-очковой конфигурации, потому что она бесконечно переключается между первым и вторым состояниями. То есть она выглядит одинаково на 1, 3, 5 и всех следующих нечётных шагах.

Турнир LEDAS "Жизнь"

Сможете ли вы получить меньше очков? Попробуйте разные конфигурации на сайте playgameoflife.com или любом подобном. Потом, скорее всего, вам понадобится Golly или другая мощная система (кстати, детям стоит запретить устанавливать Golly на телефоны, чтобы они всё же установили, а потом погрузились в чудесный мир математических исследований).

Мы приглашаем читателей isicad присылать свои решения на адрес quiz@ledas.com. В письме указывайте, пожалуйста, начальную конфигурацию и количество итераций.

Мы опубликуем имена и названия компаний всех приславших решения (если не хотите, чтобы ваше имя было опубликовано, укажите это явно, пожалуйста). Ждём ваших оригинальных решений!

Таблица результатов на 15 сентября 2020

1. Mikhail (5 * 11 + 43 * 3 = 184 очка) - 14 сентября 2020

2. Polina (7 * 11 + 39 * 3 = 194 очка) - 15 сентября 2020

3. Alex (7 * 11 + 40 * 3 = 197 очков) - 10 сентября 2020

4. Mikhail (7 * 11 + 41 * 3 = 200 очков) - 11 сентября 2020

5. Daria (18 * 11 + 34 * 3 = 300 очков) - 3 сентября 2020

6. Nine line segments (27 * 11 + 27 * 3 = 378 очков) - 1 сентября 2020

7. Empty field (48 * 11 = 528 очков) - 1 сентября 2020