Игры Джона Конвея
В.КЛЕПЦЫН
Джон Конвей (26.12.1937–11.04.2020) говорил, что не проработал ни единого дня, а только играл. Блестящий математик современности, он работал «играючи» во многих областях, и мне хочется вспомнить часть того, чем он занимался и запомнился.
Игра «Жизнь»
Пожалуй, самое широко известное открытие Конвея – это придуманная им игра «Жизнь». Устроена она так: на (бесконечной) бумаге в клеточку часть клеток объявляется «живыми» (или «заполненными», и обычно их закрашивают), а остальные «мертвыми» (или «пустыми»). После этого их конфигурация начинает (вся одновременно!) эволюционировать по следующим исключительно простым правилам: 1. Если у живой клетки в некоторый момент из 8 соседей было 2 или 3 живые клетки, то на следующий ход она выживает, в противном случае она умирает (обычно говорят, что если живых соседей 1 или 0, то она умирает «от одиночества», а если больше 3, то «от перенаселения»). 2. Если у пустой клетки ровно 3 живых соседа – то на следующем ходу в ней зарождается жизнь (а иначе она остается пустой). Так (рис.1), квадрат 2 u 2 («блок») остается неподвижным (у каждой его клетки по 3 живых соседа), линия из 3 клеток за 1 ход поворачивается на 90 градусов вокруг центра (поэтому ее называют «мигал-
Рис. 1. Блок, семафор и улей
DOI: https://doi.org/10.4213/kvant20200502
Рис. 2. Пять последовательных положений глайдера, летящего вправо-вниз
кой» или «семафором»), а прямоугольник 2 u 3 за один ход становится «ульем» (еще одной не меняющейся конфигурацией). Слово «игра» тут не совсем точное, ибо все, на что влияет «игрок», это начальная расстановка клеток, все дальнейшее от него уже не зависит. Зато за жизнью такой «колонии клеток» бывает очень интересно наблюдать. Глайдер (или планер), изображенный на рисунке 2, – конфигурация, которая движется вправо-вниз с постоянной скоростью под углом в 45 градусов. А другая невинно выглядящая конфигурация из пяти клеток – r-пентамино (рис.3) – эволюционирует на протяжении 1103 поколений. Глядя на r-пентамино, Конвей задал следующий интересный вопрос: бывают ли бесконечно растущие конфигурации? Он объявил награду в 50 долларов за решение этого вопроса – которую получил Билл Госпер, открывший глайдерное ружье, конфигурацию, постоянно «стреляющую» глайдерами. Создание глайдерного ружья через какоето время позволило доказать, что игра «Жизнь» Тьюринг-полна: любую программу, которую можно запустить на какомнибудь компьютере, можно «эмулировать» с
13
ИГРЫ
ДЖОНА
Рис.9. Позиция со значением 1 2 и уравнение для нее; бесконечный стебель со значением 1 3; два бесконечных стебля с не-вещественными значениями
нулевой (т.е. такой, где начинающий проигрывает). Для конечных графов в игре «хакенбуш» сопоставляемые им числа всегда двоично-рациональные. Но – разрешив рассматривать бесконечные «стебли бамбука» (на которых, тем не менее, партия всегда завершается за конечное время), можно получить и позиции, которым сопоставляются любые вещественные числа. Более того – оказывается, что «внутри теории игр» можно выбрать игры, которые можно объявить «числами». И естественно определить операции на них – сложение, умножение и так далее. Однако среди таких чисел будут не только все вещественные, но и многие другие. Посмотрите на три правые картинки на рисунке 9. Вторая из этих трех игр, бесконечный синий «стебель бамбука», будет соответствовать «бесконечному числу» – ординалу Z. А бесконечный стебель, в котором синее ребро только нижнее, – обратному к нему «числу» 1 Z. И все это и есть придуманные Конвеем сюрреальные числа – которые я здесь, впрочем, не определил. Об этом можно почитать в книге Пьера Деорнуа [3]; а еще сюрреальным числам (уже без связи с теорией игр) была посвящена статья [4] в «Кванте» аж в 1979 году. Чтобы завершить рассказ об играх, можно упомянуть две книги Конвея – «On Numbers and Games» и написанную в соавторстве с Берлекемпом и Ги «Winning Ways for your Mathematical Plays». Обе стали бестселлерами сразу после выхода.
Иррациональность корня из 2 Мне хочется вспомнить и очень интересную – именно для школьников – статью
КОНВЕЯ
Конвея и Шипмана [5], где собраны разные доказательства иррациональности корня из 2 (и других квадратных корней). Это действительно интересное чтение: как один и тот же результат может получаться совершенно разными методами. Конечно же, там упоминается и классическое доказательство, в котором выясняется, что и числитель и знаменатель должны оказаться четными, – но не только оно. Так, там появляется доказательство Танненбаума. А именно, если бы 2 был рационален, то можно было бы взять наименьшую пару целых чисел p, q такую, что площадь квадрата со стороной p равна сумме площадей двух квадратов со стороной q. Но поместив два таких квадрата внутрь квадрата со стороной p (рис.10, слева), мы видим, что в таком случае площадь, закрытая дважды (а это квадрат со стороной 2q p ), равна непокрытой площади (а это два квадрата со стороной p q каждый). И мы получаем противоречие с минимальностью пары p, q. А Конвей заметил, что аналогичным образом можно доказывать и иррациональность корня из 3 – оно изображено на рисунке 10 справа Еще одно из собранных в этой же статье доказательств принадлежит Миклошу Лацковичу: если раскрыть скобки в вы- ражении n
2 1, то получится число вида
A 2 B, где A и B – целые. И если бы 2
Рис. 10. Доказательство Танненбаума иррациональности 2 и его модификация Конвея для 3
1 Есть и аналогичные доказательства для
5
и 6: их можно найти в статье А.Спивака «Иррациональность корней из 2, 3, 5 и 6» («Квант», 2010, №1).