В начале игры на чистом листе бумаги рисуется несколько точек. Затем игроки по очереди ходят. Ход заключается в том, что игрок соединяет линией (прямой или кривой) две точки либо рисует петлю, начинающуюся и заканчивающуюся в какой-то точке, а потом ставит на этой линии новую точку. Правила очень простые: линии не должны пересекаться, линия не должна проходить через ранее поставленные точки, из каждой точки не должно исходить более трех точек. Победителем считается игрок, сделавший последний возможный ход. На рис. 13.13 показана игра с двумя начальными точками, в которой игрок 2 выигрывает на четвертом ходу.

Рис. 13.13. Игрок 2 выигрывает в «Рассаду»

Чем больше точек нарисовано в начале, тем дольше длится игра, но бесконечно продолжаться она не может. В начале игры с n точками существует 3n мест для присоединения ребра. После проведения каждого нового ребра количество свободных мест уменьшается на единицу (два места использованы, одно добавилось). Поэтому самая длинная игра не может продолжаться более 3п — 1 ходов.

Оказывается, что при небольших n преимущество есть у первого или второго игрока, в зависимости от числа точек. Если в начале игры всего две точки, то второй игрок всегда может делать ходы, гарантированно приводящие к выигрышу. Это верно также для n = 1, 6, 7, 8. С другой стороны, первый игрок имеет преимущество при n = 3, 4, 5, 9, 10, 11. Большая часть этих случаев (n > 6) была проверена на компьютере108. Для следующих значений n неизвестно, имеет ли какой-то игрок преимущество. Хотя теоретически эта игра несправедлива, конкретная выигрышная стратегия известна только для самых малых n. В любом случае на практике для выигрыша нужно приложить интеллектуальные усилия.

Впоследствии Конвей придумал вариант «Рассады», который назвал «Брюссельская капуста». Вначале рисуется не n точек, а n плюсиков. Игроки по очереди соединяют свободные концы плюсиков линией и ставят на ней новый плюсик (с двумя свободными концами) (см. рис. 13.14). В отличие от «Рассады», правила «Брюссельской капусты» позволяют сходиться в одной вершине четырем ребрам. Как и раньше, победителем считается игрок, сделавший последний ход. Как выяснилось, забавное название «Брюссельская капуста» было намеком на то, что и сама игра шуточная.

Мы видели, что «Рассада» обязательно заканчивается, но для «Брюссельской капусты» это не так очевидно. Каждый ход убирает два свободных конца, но и добавляет два новых, поэтому кажется, что игра может продолжаться бесконечно. Однако конец любой партии в «Брюссельскую капусту» предопределен, и в этом и состоит шутка. Какими бы гениальными или тупыми ни были игроки, игра всегда заканчивается после 5n — 2 ходов — не больше, не меньше. Иными словами, если вначале было нечетное число плюсиков, то гарантированно выиграет первый игрок, иначе лавры победителя достанутся второму игроку.

Рис. 13.14. Игрок 2 выигрывает в «Брюссельскую капусту»

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

Мы утверждаем, что игра закончится, когда граф станет связным и будет иметь ровно 4n граней (внешняя область тоже считается гранью). В начале игры имеется n плюсиков с 4n свободными концами. Поскольку каждый ход убирает два свободных конца и добавляет два новых, всегда имеется 4n свободных концов. Для любой грани должен существовать по крайней мере один свободный конец, указывающий внутрь нее, а именно тот, что принадлежит последней нарисованной линии, ограничивающей ее. Таким образом, граф имеет не более 4n граней. С другой стороны, если граней меньше 4n, то какая-то грань должна содержать два свободных конца, поэтому игра еще не закончена.

Предположим, что игра заканчивается после m ходов, и в результате получается связный граф с V вершинами, E ребрами и F = 4n гранями. (В финальной конфигурации на рис. 13.15 V = 10, E = 16, F = 8.) Как уже было сказано, на каждом из m ходов добавляется два новых ребра и одна новая вершина. Поскольку в начале игры ребер не было, а вершин было n, то в конце мы будем иметь E = 2m ребер и V = n + m вершин. По формуле Эйлера:

2 = V — E + F = (n + m) — 2m + 4n.

Отсюда m = 5n — 2.

Рис. 13.15. Финальный граф игры в брюссельскую капусту на рис. 13.14

Так что если хотите подшутить над своими ничего не подозревающими друзьями, предложите им сыграть в «Брюссельскую капусту». Разрешите им выбрать либо очередь хода, либо начальное количество плюсиков. В любом случае вы сможете гарантировать себе выигрыш.

Приложения к главе

103. Hankel (1884).

104. Hardy (1992), 94.

105. Pick (1899).

106. DeTemple (1989).

107. Gardner (1975a), 8.

108. Applegate, Jacobson, and Sleator (1991).

Глава 14

Этот красочный мир

— Иллинойс зеленый, а Индиана розовая. Ну-ка, покажи мне внизу что-нибудь розовое, если можешь. Нет, сэр, тут все зеленое.

— Гек Финн, да неужто ты воображаешь, что каждый штат в природе такого же цвета, как на карте?

— Том Сойер, для чего, по-твоему, существует карта? Ведь она сообщает нам о фактах?

— Разумеется.

— Ну, а как же она может сообщать нам о фактах, если она все врет?

— Марк Твен, «Том Сойер за границей»109

Математик Чарльз Лютвидж Доджсон (1832–1898), больше известный как Льюис Кэрролл, автор «Алисы в Стране чудес», изобрел следующую игру для двух человек. Игрок A рисует карту континента с любым числом стран. Затем игрок B раскрашивает эту карту, так чтобы соседние страны (имеющие общую границу, касание в одной точке не считается) были выкрашены в разные цвета. Для A цель игры заключается в том, чтобы нарисовать как можно более сложную карту, вынудив B использовать много цветов. Наоборот, B должен раскрасить карту в наименьшее возможное число цветов.

Простую карту типа шахматной доски можно раскрасить всего в два цвета, но даже самый неумелый картограф сможет нарисовать карту, для которой нужно три цвета. Нетрудно также нарисовать карту, требующую четырех цветов, — нужно лишь сделать так, чтобы страну окружали ровно три другие страны (как Люксембург окружают