Номер 34.20, страница 280 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 6. Элементы комбинаторики и теории вероятностей. Параграф 34. Метод математической индукции - номер 34.20, страница 280.

Условие.

34.20. В шахматном турнире участвовали $n$ шахматистов. Каждый встретился с каждым из остальных один раз, причём ни одна партия не закончилась вничью. Докажите, что по результатам турнира всех шахматистов можно пронумеровать в таком порядке, чтобы каждый предыдущий был победителем следующего.

Решение.

Данную задачу можно смоделировать с помощью теории графов. Представим каждого шахматиста в виде вершины графа, а результат партии между двумя шахматистами — в виде ориентированного ребра между соответствующими вершинами. Если игрок $A$ победил игрока $B$, мы проводим ребро от вершины $A$ к вершине $B$. Поскольку каждый играл с каждым ровно один раз и ничьих не было, для любой пары вершин $(A, B)$ существует ровно одно ребро: либо от $A$ к $B$, либо от $B$ к $A$. Такой граф называется полным ориентированным графом или турнирным графом.

Задача сводится к тому, чтобы доказать, что в любом турнирном графе с $n$ вершинами существует Гамильтонов путь — то есть путь, который проходит через каждую вершину ровно один раз. Такой путь как раз и задает требуемую нумерацию игроков $P_1, P_2, \dots, P_n$, где $P_1$ победил $P_2$, $P_2$ победил $P_3$, и так далее до $P_{n-1}$, который победил $P_n$.

Докажем это утверждение методом математической индукции по числу шахматистов $n$.

База индукции:
При $n=2$ есть два шахматиста, $P_1$ и $P_2$. Они сыграли одну партию. Поскольку ничьих нет, один из них победил. Если $P_1$ победил $P_2$, то искомый порядок — $(P_1, P_2)$. Если $P_2$ победил $P_1$, то порядок — $(P_2, P_1)$. В любом случае, такой порядок существует. Утверждение верно для $n=2$.

Индукционное предположение:
Предположим, что для любого турнира с $k$ участниками ($k \ge 2$) можно выстроить их в ряд $Q_1, Q_2, \dots, Q_k$ так, что $Q_i$ победил $Q_{i+1}$ для всех $i$ от $1$ до $k-1$.

Индукционный переход:
Рассмотрим турнир с $n = k+1$ участниками. Выберем одного из них, назовем его $P$, а остальных $k$ участников рассмотрим отдельно. По индукционному предположению, этих $k$ участников можно выстроить в требуемый ряд: $Q_1, Q_2, \dots, Q_k$, где $Q_i$ победил $Q_{i+1}$ для всех $i$ от $1$ до $k-1$.

Теперь нам нужно вставить игрока $P$ в эту последовательность, чтобы сохранить свойство "каждый предыдущий победил следующего". Рассмотрим результаты партий игрока $P$ с игроками $Q_1, Q_2, \dots, Q_k$.

Возможны три случая:

1. Игрок $P$ победил первого игрока в ряду, $Q_1$.
В этом случае мы можем поставить $P$ на первое место. Новая последовательность будет $P, Q_1, Q_2, \dots, Q_k$. Она удовлетворяет условию, так как $P$ победил $Q_1$, а для остальных пар $(Q_i, Q_{i+1})$ условие выполнено по индукционному предположению.

2. Игрок $P$ проиграл последнему игроку в ряду, $Q_k$.
В этом случае мы можем поставить $P$ в конец ряда. Новая последовательность будет $Q_1, Q_2, \dots, Q_k, P$. Она также удовлетворяет условию, так как $Q_k$ победил $P$.

3. Игрок $P$ проиграл первому игроку $Q_1$ и победил последнего игрока $Q_k$.
В этой ситуации $P$ нельзя поставить ни в начало, ни в конец. Однако, поскольку $P$ проиграл $Q_1$, а выиграл у $Q_k$, то при движении по последовательности $Q_1, Q_2, \dots, Q_k$ должен найтись такой игрок $Q_i$, который победил $P$, а следующий за ним игрок $Q_{i+1}$ проиграл $P$. Действительно, рассмотрим множество игроков, победивших $P$, и множество игроков, которым $P$ проиграл. Так как $Q_1$ победил $P$, а $Q_k$ проиграл $P$, то в последовательности $Q_1, \dots, Q_k$ обязательно найдётся такой номер $i$ ($1 \le i < k$), что $Q_i$ победил $P$, а $Q_{i+1}$ проиграл $P$. Тогда мы можем вставить $P$ между $Q_i$ и $Q_{i+1}$. Получится новая последовательность: $Q_1, \dots, Q_i, P, Q_{i+1}, \dots, Q_k$. В этой последовательности каждый предыдущий игрок победил следующего, так как $Q_i$ победил $P$, а $P$ победил $Q_{i+1}$, а все остальные отношения побед-поражений сохранились из исходной последовательности. Таким образом, мы построили искомую последовательность для $k+1$ игрока.

Мы рассмотрели все возможные случаи и в каждом из них смогли построить требуемую последовательность для $k+1$ игрока. Следовательно, мы показали, что если утверждение верно для $k$ игроков, оно верно и для $k+1$ игрока.

По принципу математической индукции утверждение верно для любого числа шахматистов $n \ge 2$. (Для $n=1$ утверждение тривиально верно).

Ответ: Утверждение доказано. По результатам турнира всех шахматистов действительно можно пронумеровать в таком порядке, чтобы каждый предыдущий был победителем следующего.