«Ігри Конвея, малюнки Ейлера та інші проблеми»

1. Гра Конвея. У «Квантиці» № 10 за 2020 рік пропонувалася наступна «гра в паростки» Дж. Конвея.

Ріс. 1

На площині намальовано N хрестиків. Двоє ходять по черзі. За хід потрібно з’єднати два вільних кінця (на початку у кожного хрестика по 4 вільних кінця) лінією, що не перетинає вже проведені, і поставити на ній засічку (при цьому утворюється два нових вільних кінця; на малюнку 1 приклад положення після двох ходів для N = 2). Той, хто не може зробити хід, програє. Хто — початківець або другий гравець — може виграти, як би не грав суперник?

Задумаємося над тим, чому партія взагалі закінчується.

Гравці ділять площину на межі (регіони). Партія закінчиться, коли кожен з 4N вільних кінців — їх кількість не змінюється в ході гри! — опиниться в окремій межі.

Подумаємо тепер, як з’являються нові грані. Кожна нова лінія або з’єднує дві компоненти зв’язності (частини) малюнка — і тоді нових граней не з’являється («хід першого типу», рис. 2, а), або з’єднує два кінці в одній компоненті зв’язності — і тоді одна грань поділяється на дві («хід другого типу», рис. 2, б).

Ріс. 2. Два типи ходів: а) мінус одна компонента зв’язковості; б) плюс одна грань

Зауважимо, що в кожній межі обов’язково залишається хоча б один вільний кінець, тому граней не може стати більше, ніж кінців.

Отже, на початку партії у малюнка N компонент зв’язковості, в кінці — одна, тому всього буде N ‑ 1 ходів першого типу. На початку партії грань одна, а в кінці — стільки ж, скільки вільних кінців, 4N, тому всього буде 4N − 1 ходів другого типу.

Тобто всього буде зроблено N ‑ 1 + 4N ‑ 1 = 5N ‑ 2 ходів. Виходить, що «гра в паростки» — це гра-жарт: що б не робили гравці, якщо число 5N ‑ 2 непарне, то робить останній хід і виграє перший, якщо чітко — другий.

Джон Конвей (John Horton Conway)

Знаменитий математик Джон Конвей (1937-2020) придумав на початку 1960-х років (разом з Майклом Патерсоном) гру в розсаду (sprouts), а вже за її мотивами — «гру в паростки» (Brussels sprouts).

Правила гри в розсаду виглядають навіть простіше: на початку на площині позначено N точок, а за хід потрібно з’єднати дві з точок лінією, що не перетинає вже наявні лінії, і поставити на ній нову крапку; при цьому з кожної точки має виходити не більше 3 ліній.

Завдання 1. Доведіть, що партія гри в розсаду закінчується не більше ніж за 3N _ 1 ходів. Покажіть, що кількість ходів залежить від дій гравців: партія може закінчитися рівно за 3N − 1 ходів, але може і швидше.

Але хто — початківець або другий гравець — може виграти, як би не грав суперник? Комп’ютерний перебір варіантів для невеликих N дозволив висунути гіпотезу: якщо N дає залишок 3, 4 або 5 при поділі на 6, то виграє перший, інакше — другий. Але це досі не доведено!

2. Формула Ейлера. Кожен знає, що у багатокутника стільки ж вершин, скільки сторін. А який аналог цього твердження для багатогранників? У багатогранника можна порахувати кількість вершин (V), ребер (E), граней (F). Але, знаючи тільки одну з цих величин, не можна визначити інші — див. таблицю.

І все ж між цими трьома величинами, як ми побачимо, є зв’язок!

Перейдемо, по-перше, до зображень багатогранників на площині, причому таким, на яких ребра не перетинаються. Наприклад, можна підійти до однієї з граней і сфотографувати багатогранник крізь неї, використовуючи надширококутний об’єктив, — отримаються картинки типу зображених на малюнку 3.

Ріс. 3

Діємо приблизно як у попередньому розділі: на чистому аркуші паперу відзначимо спочатку V вершин, а далі будемо проводити ребра по одному.

Кожне нове ребро — це лінія, яка або з’єднує дві компоненти зв’язності (рис. 4, а), не змінюючи числа регіонів, або (якщо ребро з’єднує дві вершини в одній компоненті зв’язності) ділить один з наявних регіонів на два (рис. 4, б).

Ріс. 4. Два типи ходів: а) мінус одна компонента зв’язковості; б) плюс одна грань

На початку компонент зв’язності V, наприкінці — одна; на початку вся площина являє собою один регіон, в кінці буде F регіонів (граней). Тому з E проведених ребер було V — 1 першого типу і F — 1 другого типу. Отже, E = (V ‑ 1) + (F ‑ 1). Ми отримали наступну формулу Ейлера.

Якщо у багатогранника V вершин, E ребер, F граней, то V ‑ E + F = 2.

На площині можна намалювати правильний N-вугільник для будь-якого N. А ось правильних багатогранників існує всього п’ять! І це можна довести за допомогою формули Ейлера.

Але спочатку потрібно дати визначення правильного багатогранника (як не дивно, це не так просто). Ми приймемо таке: випуклий багатогранник називається правильним, якщо всі його грані — правильні багатокутники, а в кожній вершині сходиться одна і та ж кількість граней.

Завдання 2. а) Виведіть з формули Ейлера, що якщо у багатогранника всі грані — n-вугільники, а в кожній вершині сходиться по k граней, то

( frac{1}{n} + frac{1}{k} = frac{1}{2} + frac{1}{E}. )

б) Доведіть, що всі правильні багатогранники зображені на малюнку 5 (тобто n = 3, k = 3, або n = 3, k = 4, або n = 4, k = 3, або n = 3, k = 5, або n = 5, k = 3).

Ріс. 5

Можна перетворити малювання подібних картинок на гру. На її початку на площині позначено N точок, причому ніякі 3 не лежать на одній прямій. Двоє по черзі з’єднують якусь пару зазначених точок відрізком, що не перетинає вже проведені, поки картинка не розіб’ється на трикутники. Той, хто не може зробити хід, програє.

Завдання 3. а) Хто виграє, якщо спочатку позначені вершини правильного N-вугільника?

б) Доведіть, що як би не були розташовані точки, виходить гра-жарт: хто виграє, не залежить від дій гравців.

3. Докази і спростування. Чи існує багатогранник, всі межі якого — шестикутники?

Нехай у такого багатогранника F граней. У кожній межі 6 ребер, а кожне ребро входить рівно в 2 грані — значить, 2E = 6F. У кожній межі 6 вершин, в кожній вершині сходиться не менше 3 граней — значить, 3V — 6F. Отже, E = 3F, V ^ 2F. Але тоді V ‑ E + F ^ 2F ‑ 3F + F = 0. А за формулою Ейлера ця сума повинна бути рівна 2. Значить, таких багатогранників не буває.

З аналогічних причин не буває багатогранника, всі межі якого семикутники (і т. д.). Але приклади таких багатогранників наведені в «Квантиці» № 4 за 2020 рік! (Нотатка «Багатогранник із семикутників?»).

Мораль тут така: хоча наведене міркування «по суті правильне», повним доказом його вважати не варто, а спиратися на «приблизно зрозумілі» міркування — справа небезпечна…

Закінчимо цитатою з однойменної з цим розділом книги І. Лакатоша, яка вся складається з обговорення доказів формули Ейлера і виникаючих при цьому питань:

Сигма! Але ж нічого не встановлено. Ми не можемо зупинитися тепер.

Вчитель. Співчуваю вам. Ця остання стадія дасть важливі джерела їжі для нашої дискусії. Але наукове дослідження «починається і закінчується проблемами». (Залишає класну кімнату.)

Бета! Але спочатку у мене не було проблем! А тепер у мене немає нічого, крім проблем!

Художник Марія Усеїнова