Два связиста играют в такую игру. Имеются $n$ телефонных узлов, и связисты по очереди соединяют кабелем два из них по своему выбору. Выигрывает тот, после хода которого с любого узла можно будет дозвониться до любого другого (быть может, через несколько промежуточных; начало игры изображено на рисунке 3).
Рис. 3
Выясните, кто выигрывает при $n = 4$, 5, 6, 7, 8 — начинающий или его партнёр?
Каков ответ при произвольном $n$?
Рассмотрите также два видоизменённых варианта игры:
Пусть игрок, связавший все узлы, проигрывает. Ответьте на вопросы пунктов а) и б) для этой новой игры.
Пусть вначале все узлы попарно связаны кабелем, а связисты убирают по очереди по одному соединению. Игрок, нарушивший связь в схеме, проигрывает. Вопрос тот же: кто выигрывает при правильной стратегии для $n=4$, 5, 6, 7, 8? для произвольного $n$?
Замечание. Можно было бы рассмотреть четвёртый вариант: считать, что в пункте г) игрок, нарушивший связь, выигрывает. Полное исследование этого варианта игры автору неизвестно.
а) При $n=4$, 7, 8 выигрывает первый игрок, при $n=5$, 6 — второй; это будет следовать из решения общей задачи б).
б) Будем называть группу узлов связной, если любые два входящие в неё узла соединены (может быть, через несколько других узлов). Связную группу узлов будем называть компонентой, если ни один из входящих в неё узлов не соединён ни с одним из узлов, в ней не содержащихся. Ясно, что любой граф (система как‑то соединённых узлов) состоит из одной или нескольких компонент.
При любой игре противников настанет момент, когда множество всех узлов окажется разбитым на три компоненты $A_1$, $A_2$, $A_3$. Пусть $a_1$, $a_2$, $a_3$ — количество узлов в этих компонентах. Ясно, что проигрывает тот из игроков, кому придётся первым соединить какие‑то две из этих компонент. Критическая ситуация возникает, когда все возможные соединения внутри компонент $A_1$, $A_2$, $A_3$ будут осуществлены.
Ясно, что с начала партии до наступления такого момента будет сделано
$$
N=\dfrac{a_1(a_1-1)}2+\dfrac{a_2(a_2-1)}2+\dfrac{a_3(a_3-1)}2=\dfrac{a_1^2+a_2^2+a_3^2-n}2
$$
ходов. Если число $N$ окажется чётным, то первый игрок проигрывает, если же нечётным — то выигрывает. Чётность числа $N$, очевидно, определяется остатком, который даёт число $a_1^2+a_2^2+a_3^2-n$ при делении на 4. Так как остаток от деления на 4 числа $a_1^2+a_2^2+a_3^2$ равен количеству нечётных чисел среди чисел $a_1$, $a_2$, $a_3$ (убедитесь в этом), первый игрок должен добиваться того, чтобы количество нечётных чисел среди $a_1$, $a_2$, $a_3$ не совпадало с остатком от деления $n$ на 4. Второй же, наоборот, должен стремиться к их совпадению.
В дальнейшем компоненты с чётным числом узлов мы будем называть чётными, а с нечётным числом узлов — нечётными.
Рассмотрим отдельно четыре случая: $n=4k$, $n=4k+1$, $n=4k+2$, $n=4k+3$.
1°. $n=4k$. Первый игрок добивается победы, играя следующим образом. Пока компонент более трёх, он играет так, чтобы после каждого его хода получалось не более одной чётной компоненты: если в какой‑то момент возникают две чётные компоненты, он тут же объединяет одну из них с нечётной. В момент появления трёх компонент (независимо от того, после чьего хода это произойдёт) две компоненты будут нечётными, а одна чётной. Число $N$ при этом нечётно, первый игрок выигрывает.
2°. $n=4k+1$. В этом случае выигрывает второй игрок, поскольку он может играть так, чтобы после каждого его хода было не менее двух чётных компонент (убедитесь в этом). При этом среди чисел $a_1$, $a_2$, $a_3$ два непременно будут чётными, а одно — нечётным. Независимо от того, чей ход приведёт к образованию трёх компонент.
3°. $n=4k+2$. И в этом случае выигрывает второй игрок, применяя стратегию первого игрока в случае $n=4k$, так как при $n=4k+2$ среди чисел $a_1$, $a_2$, $a_3$ будут два нечётных.
4°. $n=4k+3$. Этот случай наиболее интересен.
При $n=3$, очевидно, выигрывает второй игрок.
Докажем, что при $n=7$ выигрывает первый игрок.
Если первый игрок своим первым ходом соединяет какие‑то два узла $A$ и $B$, второй игрок — два других узла $C$ и $D$ (рис. 1), то первый игрок выигрывает, применяя стратегию второго игрока для случая $n=4k+1$. Если же второй игрок соединяет уже $A$ или $B$ с третьим узлом $C$, то вторым ходом первый игрок замыкает треугольник, соединяя узлы $C$ и $B$ (рис. 2). Второй игрок при этом любым ответным ходом создаёт чётную компоненту. После этого первый игрок добивается того, чтобы после каждого его хода было не меньше двух чётных компонент. Среди чисел $a_1$, $a_2$, $a_3$ как и в случае $n=4k+1$, будут два чётных, что в данном случае обеспечивает победу первому игроку.
Рис. 1Рис. 2
в) Этот пункт аналогичен предыдущему. При любой игре противников настанет момент, когда множество узлов разобьётся на две компоненты $A_1$, $A_2$ из $a_1$, $a_2$ узлов. Проигрывает тот из игроков, кому придётся соединить компоненты $A_1$, $A_2$. Рассуждая так же, как и раньше, получим, что до наступления критического момента будет сделано $N=\dfrac{a_1^2+a_2^2-n}2$ ходов.
Вновь рассмотрим те же четыре случая.
1°. $n=4k$. Второй игрок выигрывает, добиваясь того, чтобы после каждого его хода было две чётные компоненты (при этом $N$ чётно).
2°. $n=4k+1$. Выигрывает второй игрок, так как, независимо от хода игры, одно из чисел $a_1$, $a_2$ будет нечётным, а $N$ чётно.
3°. $n=4k+2$. Первый игрок при $k\ge1$ добивается победы так же, как в случае 4° пункта б); ему достаточно следить, чтобы после каждого его хода, кроме, может быть, второго, было не менее двух чётных компонент, чего он и добивается (см. рисунки 1, 2).
4°. $n=4k+3$. Выигрывает первый игрок, независимо от хода игры (докажите!).
г) Назовём связную группу узлов $B_1$, $B_2$, $\ldots$, $B_m$ циклом, если узел $B_1$ соединён с узлом $B_2$, узел $B_2$ — с узлом $B_3$, $\ldots$, а узел $B_m$ соединён с узлом $B_1$. Ясно, что если в связной системе узлов есть циклы, то и игрок, делающий очередной ход, не проигрывает: он может разорвать любое из соединений в любом цикле.
Таким образом, выигрывает тот из игроков, после чьего хода в системе не остаётся циклов. Докажем, что в связной системе из $n$ узлов, не содержащей циклов (такая система в теории графов называется деревом), имеется ровно $n-1$ соединений. Для этого зафиксируем какой‑нибудь узел $B$ и заметим, что существует единственный путь, ведущий из $B$ в любой другой узел. Вдоль всех путей, выходящих из $B$, расставим стрелки, показывающие направление от $B$. В каждый из узлов, кроме $B$, входит ровно одна стрелка и, значит, общее число стрелок равно $n-1$.
Таким образом, дерево образуется после
$$
N=\dfrac{n(n-1)}2-(n-1)=\dfrac{(n-1)(n-2)}2
$$
ходов. Следовательно, при $n=4k$ и $n=4k+3$ выигрывает первый игрок ($N$ нечётно), а при $n=4k+1$ и $n=4k+2$ — второй ($N$ чётно).
