Рекурренты в комбинаторике и числа Фибоначчи f(n)
Ошибка.
Попробуйте повторить позже
Есть 
отрезков длины 
, 
, …, 
, где 
, 
, а при 
выполнено 
. Сколькими способами эти
отрезки можно разбить на четвёрки так, чтобы из отрезков каждой четвёрки можно было составить четырёхугольник?
Источники:
Подсказка 1
Подумайте, при каком условии из четырех отрезков можно составить четырехугольник. Вспомните аналогичное условие для треугольников.
Подсказка 2
Да, из отрезком a < b < c < d можно составить четырёхугольник <=> a+b+c > d, попробуйте рассмотреть произвольную четвёрку, которая образует четырёхугольник и расписать свойство x_k = x_{k-1} + x_{k-2} более подробно, т.е. для x_{k-1} применить его же и посмотреть чему тогда должно быть равно c и b.
Подсказка 3
Верно, если d = x_{k}, то b = x_{k-2}, c = x_{k-1}, иначе четырёхугольник не построится. Теперь задача свелась к подсчету количества способов выбрать n пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной тройки.
Подсказка 4
Введем понятие "хорошей" последовательности, состоящей из 2n чисел, в которой каждое из чисел 1, ..., n участвует ровно два раза. Как мы можем восстановить способ разбиения последовательности отрезков по хорошей последовательности? Может мы можем первому вхождению числа в "хорошую" последовательность сопоставить число, а второму - тройку?
Подсказка 5
Теперь давайте подсчитаем количество хороших последовательностей. Сколькими способами можно выбрать индексы для двух единиц? А сколько тогда останется возможных индексов для двух двоек? А сколько всего получится способов сопоставить каждому числу 2 индекса?
Подсказка 6
А не посчитали ли мы что-либо несколько раз? Меняет ли перестановка чисел в "хорошей" последовательности набор отрезков?
Из отрезков 
можно сложить четырехугольник тогда и только тогда, когда 
. Рассмотрим четверку
, заметим, что 
, следовательно, 
, иначе проверяемое
неравенство не выполнено. Аналогично, можно показать, что 
.
Назовем последовательность 
интересной. Таким образом, необходимо посчитать количество способов выбрать в интересной
последовательности 
пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной
тройки.
Рассмотрим последовательность, состоящую из 
чисел, в котором каждое из чисел 
участвуют ровно два раза и назовем ее
хорошей. Восстановим по хорошей последовательности способ разбиения интересной последовательности. На первом шаге рассмотрим первое
число в каждой из последовательности. На каждом следующем шаге, если рассматриваемое число в хорошей последовательности
встречается впервые, то ставим ему в соответствие рассматриваемое число в интересной последовательно, после чего рассматриваем
следующий числа в каждой из последовательностей. Если рассматриваемое число в хорошей последовательности встречается во второй раз,
то ставим ему в соответствие тройку из рассматриваемого элемента в интересной последовательности и двух элементов, идущих
после него. Таким образом, к концу процесса, каждому первому вхождению числа в хорошей последовательности стоит в
соответствие один элемент интересной последовательности, а каждому второму тройка подряд идущих элементов интересной
последовательности.
Посчитаем количество хороших последовательностей. Существует 
способов выбрать индексы двум единичкам, после этого
останется 
возможных индекса, следовательно, существует ровно 
способов выбрать индексы для двух двоек. Продолжая
ставить каждому из чисел в соответствие два индекса, получим что общее количество способов сделать это, равно 
. Осталось
заметить, что каждая перестановка чисел в хорошей последовательности не меняет набор разбиение интересной последовательности,
следовательно, каждое разбиение было посчитано 
раз (количество перестановок длины 
), а значит общее количество разбиений
равно
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
