Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
Рис. 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
Этот красочный мир
— Иллинойс зеленый, а Индиана розовая. Ну-ка, покажи мне внизу что-нибудь розовое, если можешь. Нет, сэр, тут все зеленое.