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