Индукция в комбинаторике

Докажем утверждение по индукции. База очевидна. Переход будем делать, добавляя по человека. Пусть для человек их можно расставить, как требуется по условию. Покажем, что и тоже можно. Выделим в этих самую длинную цепочку, подходящую по условию. По предположению индукции там хотя бы человек.

1.

Предположим, что там человек. Без ограничения общности, можно считать, что крайние люди и проиграли своим соседям (по чётности их результаты будут одинаковы). Будем писать если выиграл у Без ограничения общности, можно считать, что Рассмотрим оставшегося человека Если он выиграл у или у то можно увеличить цепочку, добавив на край. Значит, и Тогда переставим на другой край, а потом на тот же край поставим Получим подходящую цепочку Мы в любом случае сможем добавить человека что и хотели.

2.

Предположим, что там человек. Тогда уберём одного с краю, останется три человека. Опять можно считать, что крайние люди и проигравшие и . Пусть их зовут Среди них обязательно есть человек, который одному проиграл, а у другого выиграл. Пусть это и Посмотрим, как сыграл с Если то добавим на край после а потом Получим корректную цепочку Теперь в ней человек, противоречие. Пусть Тогда перекинем на другой край, допишем за ним а дальше Снова получим цепочку, которая теперь кончается на и в ней человек. Так что мы всегда сможем найти увеличить нашу цепочку, пока в ней не станет человек, ЧТД.