Любая колония имеет преемника, но не у каждой есть предшественник. Такие изолированные колонии называются садами Эдема. Сад Эдема можно увидеть, только если поместить его на плоскость в качестве начальной конфигурации. Подумайте, как использовать вашу программу для нахождения сада Эдема.
Литература
Беркс (ред.) (Burks A. W. (Ed.)). Essays on Cellular Automata. University of Illinois Press, Urbana, IL, 1970.
Кодд (Codd E. F.). Cellular Automata. Academic Press, New York, NY, 1968.
Обе эти книги значительно серьезнее статей Гарднера в Scientific American. Вторая из названных книг познакомит вас с основами предмета, а книга Беркса представляет собой сборник разнородных статей, охватывающих всю область клеточных автоматов. После изучения этих книг читателю будет доступен практически весь математический материал.
Гарднер (Gardner Martin). Mathematical Games. Scientific American, 223, 10, pp. 120–123, October 1970, and 224, 2, pp. 112–117, February 1971. [Имеется перевод: Гарднер М. Математические досуги. — Мл Мир, 1972, с. 458.]
Мартин Гарднер описал игру Жизнь в своей колонке журнала, и это вызвало такой отклик читателей, что он вынужден был немедленно (по меркам ежемесячного журнала) посвятить ей еще одну колонку. Игра Жизнь, несомненно, принесла славу Джону Хортону Конвею, ее талантливому и продуктивному изобретателю. В более поздних статьях содержится много дополнительного материала об игре Жизнь, а также о других работах Конвея.
Уэйнрайт (ред.) (Wainwright R. Т. (Ed.)). Lifeline. 1280 Edcris Road, Yorktown Heights, NY 10598.
Lifeline — ежеквартальный журнал, посвященный Жизни и родственным темам. Ориентированный на фанатиков этой игры, журнал содержит всевозможную информацию о Жизни, и его чтение может оказаться захватывающим занятием.
3.
Папочка, а почему море синее?
или Раскрашивание карты методом исчерпывающего поиска
Чтобы на географической карте было удобно различать регионы, ее раскрашивают по следующему правилу: два региона должны быть окрашены в разные цвета, если их границы имеют более чем конечное число общих точек. (Обычно составители карт не страдают топологическими патологиями и не ищут вырожденных примеров, противоречащих здравому смыслу.) С другой стороны, картографам предстоит оплачивать типографские счета, поэтому, чем меньше цветов будет использовано, тем лучше. В частности, картографы, расписывающие карту как попало, распишутся лишь в своем легкомыслии: им придется использовать больше красок, чем это необходимо. Свои действия нужно планировать заранее. Итак,
