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

Докажем, что в аналогичной задаче для шеренги из детей наибольшее возможное количество хороших пар равно

Пронумеруем детей числами в порядке убывания роста. Тогда, если расставить детей в порядке

то все пары где окажутся хорошими; таких пар всего Кроме этого, все пары вида также окажутся хорошими; таких пар всего При этом пара учтена дважды, так что общее количество хороших пар равно

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

Пусть теперь Рассмотрим произвольную шеренгу и выберем в ней хорошую пару в которой — наибольшее; пусть для определённости и ребёнок стоит левее, чем Назовём ребёнка прекрасным, если он образует хорошие пары как с так и с

______________________________________________________________________________________________________________________________________________________

Лемма. Существует не больше двух прекрасных детей.

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

Предположим, что есть два прекрасных ребёнка стоящих левее тогда

Ребёнок не может стоять между и иначе пара не хорошая; поэтому стоит левее Но тогда стоит между и и пара — не хорошая, что невозможно. Это противоречие показывает, что левее стоит не более одного прекрасного ребёнка. Аналогично, не более одного стоит правее откуда и следует доказываемое утверждение.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь несложно совершить переход индукции. Выкинув и мы получим, что все хорошие пары, не содержащие и остались хорошими; по предположению индукции, их не больше, чем Осталось оценить количество хороших пар, содержащих или Это пара пары и для любого прекрасного ребёнка и максимум по одной из пар и для остальных детей Всего получаем не более чем

откуда общее количество хороших пар не превосходит

что и требовалось доказать.