Мы видели, что «Рассада» обязательно заканчивается, но для «Брюссельской капусты» это не так очевидно. Каждый ход убирает два свободных конца, но и добавляет два новых, поэтому кажется, что игра может продолжаться бесконечно. Однако конец любой партии в «Брюссельскую капусту» предопределен, и в этом и состоит шутка. Какими бы гениальными или тупыми ни были игроки, игра всегда заканчивается после 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 должен раскрасить карту в наименьшее возможное число цветов.
Простую карту типа шахматной доски можно раскрасить всего в два цвета, но даже самый неумелый картограф сможет нарисовать карту, для которой нужно три цвета. Нетрудно также нарисовать карту, требующую четырех цветов, — нужно лишь сделать так, чтобы страну окружали ровно три другие страны (как Люксембург окружают Германия, Франция и Бельгия). Поскольку каждая из четырех стран граничит с тремя другими, необходимо четыре цвета (еще два примера дают Парагвай и Малави).
Во введении мы видели более тонкий случай, когда требуется четыре цвета. Столько необходимо для раскрашивания Невады, Калифорнии, Аризоны, Юты, Айдахо и Орегона, потому что Невада окружена нечетным числом стран (рис. 14.1). Оказывается, что Невада, Западная Вирджиния и Кентукки — единственные штаты США, для которых имеет место такая проблема. Правильно раскрасив эти штаты и их соседей, мы сможем распространить раскраску на все США, так что четвертый цвет придется использовать всего два раза.