Высшая проба 2024, 11 класс, задача 4
( баллов) Есть отрезков длины , где , , а при выполнено . Сколькими способами эти отрезки можно разбить на четвёрки так, чтобы из отрезков каждой четвёрки можно было составить четырёхугольник?
Ответ
Решение.
Ясно, что из четырёх отрезков можно составить четырёхугольник тогда и только тогда, когда . Потому из четырёх чисел Фибоначчи , , , () можно составить треугольник тогда и только тогда, когда , (в этом случае , а иначе , то есть иначе нельзя).
То есть подходят четвёрки образованные какими-то тремя последовательными числами Фибоначчи и ещё одним меньшим их, и только такие четвёрки подходят. Перейдём от чисел Фибоначчи к их номерам: понятно, что искомых разбиений столько же, сколько разбиений на четвёрки чисел от до таких, что в каждой четвёрке есть три последовательных числа и одно меньшее их, поэтому далее считаем количество таких разбиений.
В каждом таком разбиении пронумеруем четвёрки натуральными числами от до всеми возможными способами (этим мы домножим количество способов на ). Далее посчитаем количество способов разбить отрезки на такие занумерованные четвёрки.
Выберем произвольное разбиение на занумерованные четвёрки, пройдём по возрастанию по числам от до , проходя меньший элемент в -й четвёрке запишем «над ним» число , проходя тройку больших элементов в -й четвёрке запишем «над ней» число . Таким образом разбиению сопоставилась последовательность из чисел, в которой каждое из чисел встречается ровно раза.
Это соответствие взаимно однозначное, так как есть обратное: выберем произвольную такую последовательность из чисел, последовательно пройдёмся по её членам, записывая последовательные натуральные числа (начиная с единицы) и относя их к четвёркам следующим образом: встретив число в первый раз — запишем «над ним» одно следующее число и отнесём его к -й четвёрке, а встретив во второй раз — запишим «над ним» три следующих натуральных числа и отнесём их к -й четвёрке. Ясно, что будут выписаны в точности числа от до и для каждого натурального не превосходящего к -й четвёрке будут отнесены четыре числа образующим подходящую четвёрку. По построению тривиально, что построенные соответствия вазаимно обратны друг другу.
Итак, количество разбиений на занумерованные четвёрки совпадает с количеством последовательностей из чисел, в которых каждое из чисел встречается ровно раза. А таких последовательностей ровно . Разделив на , получаем окончательный ответ на исходный вопрос задачи:
Ответ: $(2n-1)!!