Всесиб 2022, 11 класс, задача 3

Ответ. .

Обозначим числа нашей перестановки слева направо за .

Решение 1. Пойдём с конца. Последнее число забавной перестановки либо больше, либо меньше всех чисел множества , следовательно, оно равно или . Предпоследнее число забавной перестановки либо больше, либо меньше всех чисел множества , кроме , то есть это наименьший или наибольший элемент во множестве или во множестве . В каждом из случаев есть ровно две возможности выбора, варианты для двух последних чисел перестановки выглядят так: , , , . Несложно убедиться, что при любом первые чисел перестановки образуют интервал из подряд идущих чисел из множества , а число является в этом интервале минимальным или максимальным - всего две возможности, кроме самого первого числа , для которого остаётся единственная возможность. Всего получаем ровно возможностей выбора.

Решение 2. Пусть , где - одно из чисел . Любое число , меньшее , будет по условию также меньше и всех чисел, меньших и стоящих левее , поэтому все числа забавной перестановки, меньшие , образуют в ней убывающую подпоследовательность. Аналогично, все числа, большие , образуют в ней возрастающую подпоследовательность. При этом любое взаимное расположение этих подпоследовательностей удовлетворяет условию и приводит к забавной перестановке.

Следовательно, любая забавная перестановка полностью задаётся значением её первого элемента и номерами мест, на которых в убывающем порядке слева направо расположены числа среди всех членов забавной перестановки, кроме первого. Остальные места автоматически заполнятся числами в порядке возрастания. Следовательно, при фиксированном количество забавных перестановок равно числу сочетаний , а общее их количество равно сумме .

Решение 3. Пойдём с начала, рассмотрим, как меняется множество первых чисел забавной перестановки при увеличении . В качестве можно взять любое натуральное число из интервала , и . Пусть на -ом шаге уже выбраны числа , обозначим за и соответственно минимальное и максимальное их них.

Докажем, что очередное должно равняться либо , либо . Действительно, если , сразу нарушается условие забавности, так как расположено правее и , но больше одного из них и меньше другого. Если , то число не входит в и ещё не использовано в перестановке, значит, оно будет расположено в ней где-то правее , тогда тройка нарушает условие забавности, так как при этом меньше , но больше , стоящих левее него. Аналогично доказывается, что предположение также нарушает условие забавности. Остаётся только или .

Из доказанного следует, что для каждого множество состоит из некоторых последовательных чисел из интервала , и получается из него добавлением числа, соседнего с этим интервалом слева или справа. Значит, забавная перестановка при данном подходе однозначно задаётся первым числом и последовательностью добавлений нового числа слева и справа от уже использованных, из которых будут добавлением чисел слева и - добавлением чисел справа. Последовательность же добавлений однозначно определяется номерами добавлений слева. Следовательно, при фиксированном первом числе количество забавных перестановок равно числу сочетаний , а общее их количество равно сумме .

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

Решение 4. Индукцией по докажем, что для произвольного количество забавных перестановок равно . База индукции: при и оно, очевидно, равно и .

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