Пагінці (гра)

«Пагінці» (англ. Sprouts) — топологічна гра, яка полягає в тому, що гравці (зазвичай двоє) за певними правилами малюють лінії на папері. Гру винайшли математики Джон Конвей та Майкл Патерсон у Кембриджському університеті на початку 1960-х.

Правила гри

Суть гри така: перед початком гри на папері малюють кілька крапок (їх можна назвати насінням). Про кількість первинних крапок домовляються перед грою.

Гравці ходять почергово. Кожен хід гравця полягає в тому, що він або з'єднує дві точки лінією (можливо кривою), або малює лінію-петлю, що починається в якійсь точці і в ній же закінчується («пагінець проростає»).

На кожній проведеній лінії малюють одну нову крапку; нові точки рівноправні початковим (від них також можна проводити лінії, на кожній з яких також малюють по одній крапці).

При цьому потрібно дотримуватися таких правил:

Лінії не повинні перетинатися (перетини лінії із самою собою теж неприпустимі).
Проведена лінія не повинна проходити через раніше поставлені точки, які не є початком або кінцем цієї лінії.
З кожної точки не повинно виходити більш ніж три лінії. Саме тому до нової крапки не можна домалювати петлю, бо інакше отримаємо 4 лінії, що виходять з однієї точки (петлю вважають двома лініями, які виходять з цієї точки).

Програє той гравець, який не зможе зробити хід, коли хід перейде до нього. Можна також грати в піддавки — в цьому випадку той, хто ходить останнім, вважається не переможеним, а переможцем.

Аналіз гри «Пагінці»

Відома формула, за допомогою якої, знаючи початкову кількість точок, можна обчислити максимально можливу кількість ходів всіх гравців:

K=3\cdot N-1

,

де К — максимально можлива кількість ходів;
N — кількість первинних точок.

Ця формула, однак, дає лише оцінку зверху для максимально можливої кількості ходів.

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

Відома також оцінка знизу: гра не може закінчитися раніше, ніж через $2N$ ходів.

Історія гри

Винахідниками гри «Пагінці» є професор Джон Конвей та кембриджський аспірант Майкл Стьюарт Патерсон^[en]. Джон Конвей найбільш відомий світові завдяки грі «Життя», яку він створив — клітинному автомату, що моделює життя створеної гравцем колонії організмів.

Вони винайшли гру «Пагінці» 21 лютого 1967.

Майже одразу гра стала популярною, принаймні в Кембриджському університеті.

Псевдогра «Брюссельська капуста»

«Брюссельська капуста» — хід гри при двох початкових хрестиках.

Пізніше Конвей винайшов іншу гру, точніше псевдогру, схожу на «Пагінці».

У «Брюссельській капусті» перед грою замість декількох точок малюють кілька маленьких хрестиків (хрестик — крапка з чотирма короткими променями). Кожен хід складається зі з'єднання лінією двох вільних променів хрестиків (променів різних хрестиків або одного) та малювання нового хрестика посередині шляхом перекреслення лінії в деякій точці. Кожен промінь можна використовувати для ходу лише один раз (після того, як від або до цього променю походили, промінь вважається невільним та ходити від/до нього більше не можна). Так само як у «Пагінцях», лінії не повинні перетинатися і проходити через раніше поставлені хрестики, які не є початком або кінцем лінії. Кожну проведену лінію перетинають рискою, що являє собою створення на цій лінії нового хрестика, у якого два протилежних промені лежать на щойно проведеній лінії, а інші два протилежних промені вільні. Виграш в «Брюссельської капусті» визначається так само, як у «Пагінцях».

Строго кажучи, «Брюссельська капуста» не є грою, оскільки кількість ходів в ній не залежить від майстерності гравців: як би гравці ні ходили, «гра» завжди закінчується через $5N-2$ кроків (де $N$ — кількість первинних хрестиків). Збільшуючи число хрестиків на початку, отримуємо послідовність чисел, які почергово парні та непарні.

Отже, «Брюссельська капуста» не придатна для змагання, «гімнастики розуму», але, користуючись правом обирати кількість хрестиків на початку або право ходити першим чи другим, можна завжди вийти переможцем з цієї гри. Таким чином, можна укладати безпрограшне парі щодо виграшу.

Обґрунтування формули числа кроків у грі «Брюссельська капуста»

Пояснення цього факту є елементарним і доступне будь-кому, хто знайомий з таким поняттям, як Ейлерова характеристика. Нехай гра закінчилась через $M$ кроків, тобто той гравець, черга якого ходити, не може з'єднати жодних двох хрестиків. Поле гри являє собою плоский граф. Обчислимо кількість його вершин (хрестиків) $B$ . Очевидно, що на кожному кроці гри додавався один хрестик, а спочатку було $N$ хрестиків, тому $B=N+M$ .

Знайдемо кількість ребер $P$ — ліній, що з'єднують вершини. Спочатку всі хрестики були роз'єднані, а на кожному кроці ми додавали по 1 вершині і, відповідно, по 2 ребра $P=2M$ . Гранню ж називатимемо область, яка обмежується замкненою кривою — частиною досліджуваного графа. Також гранню називається зовнішність графа. Бачимо, що в кожній грані є рівно один вільний промінь, що виходить з вершини (два бути не може, бо тоді їх можна було б з'єднати, а існування хоча б одного очевидно з самого процесу побудови). Тому кількість граней збігається з кількістю променів, що виходять з вершин. На початку гри з кожної вершини виходило по 4 промені, при цьому на кожному кроці 2 промені були використані і 2 нові з'являлись. Таким чином, кількість променів (а, відповідно, і граней) — величина незмінна й залежить тільки від початкової кількості вершин: $\Gamma =4N$ .

Отриману картинку можна розглядати як тріангуляцію площини. Відомо, що ейлерова характеристика площини $B-P+\Gamma =2$ . Підставимо відомі величини: $N+M-2M+4N=2$ , звідки $M=5N-2$ .

Література

Мартін Гарднер — «Математичні новели».