ВсОШ 2024, 9 класс, задача 8
детей, среди которых нет двух одинакового роста, выстроились в шеренгу. Назов ем пару различных детей хорошей, если между ними не стоит ребёнка, рост которого больше роста одного из и , но меньше роста другого. Какое наибольшее количество хороших пар могло образоваться? (Пары и считаются одной и той же парой.) ( И. Богданов )
Ответ
Ответ. .
Решение. Докажем, что в аналогичной задаче для шеренги из детей наибольшее возможное количество хороших пар равно .
Пронумеруем детей числами в порядке убывания роста. Тогда, если расставить детей в порядке
,
то все пары , где , окажутся хорошими; таких пар всего . Кроме этого, все пары вида также окажутся хорошими; таких пар всего . При этом пара учтена дважды, так что общее количество хороших пар равно .
Осталось доказать, что хороших пар не может быть больше, чем . Сделаем это индукцией по . При утверждение тривиально, ибо есть всего одна пара детей.
Пусть теперь . Рассмотрим произвольную шеренгу и выберем в ней хорошую пару , в которой - наибольшее; пусть для определённости , и ребёнок стоит левее, чем . Назовём ребёнка прекрасным, если он образует хорошие пары как с , так и с .
Лемма. Существует не больше двух прекрасных детей.
Доказательство. Если прекрасен, то по выбору пары имеем и , откуда . Такой ребёнок не может стоять между и , иначе пара не была бы хорошей; значит, любой прекрасный ребёнок стоит либо слева от , либо справа от .
Предположим, что есть два прекрасных ребёнка , стоящих левее ; тогда . Ребёнок не может стоять между и , иначе пара не хорошая; поэтому стоит левее . Но тогда стоит между и , и пара - не хорошая, что невозможно. Это противоречие показывает, что левее стоит не более одного прекрасного ребёнка. Аналогично, не более одного стоит правее , откуда и следует доказываемое утверждение.
Теперь несложно совершить переход индукции. Выкинув и , мы получим, что все хорошие пары, не содержащие и , остались хорошими; по предположению индукции, их не больше, чем . Осталось оценить количество хороших пар, содержащих или . Это пара , пары и для любого прекрасного ребёнка , и максимум по одной из пар и для остальных детей . Всего получаем не более чем пар, откуда общее количество хороших пар не превосходит , что и требовалось доказать.
Замечание. Пару детей и , для которых верно утверждение леммы, можно выбирать разными способами. Можно, например, выбрать хорошую пару, в которой дети стоят дальше всего друг от друга. Другой способ - выбрать и найти наибольшее такое, что - хорошая пара.