Тема . Высшая проба

Комбинаторика на Высшей пробе: клетки, комбигео, игры, графы

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела высшая проба
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#80741

Есть 4n  отрезков длины x
 1  , x
 2  , …, x
 4n  , где x = 1
 1  , x  =2
 2  , а при k> 2  выполнено x = x  + x
k   k−1   k−2  . Сколькими способами эти отрезки можно разбить на четвёрки так, чтобы из отрезков каждой четвёрки можно было составить четырёхугольник?

Источники: Высшая проба - 2024, 11.4 (см. olymp.hse.ru)

Показать ответ и решение

Из отрезков a< b< c< d  можно сложить четырехугольник тогда и только тогда, когда a+ b+ c> d  . Рассмотрим четверку xs < xi < xj < xk  , заметим, что xk =xk−1+ xk−2 = 2xk−2 +xk−3 > xk−2+xk−3+ xk−4  , следовательно, xj = xk−1  , иначе проверяемое неравенство не выполнено. Аналогично, можно показать, что xi =xk−2  .

Назовем последовательность     4n
{xi}i=1  интересной. Таким образом, необходимо посчитать количество способов выбрать в интересной последовательности n  пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной тройки.

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

Посчитаем количество хороших последовательностей. Существует C22n  способов выбрать индексы двум единичкам, после этого останется 2n− 2  возможных индекса, следовательно, существует ровно C22n−2  способов выбрать индексы для двух двоек. Продолжая ставить каждому из чисел в соответствие два индекса, получим что общее количество способов сделать это, равно (2n)!∕2n  . Осталось заметить, что каждая перестановка чисел в хорошей последовательности не меняет набор разбиение интересной последовательности, следовательно, каждое разбиение было посчитано n!  раз (количество перестановок длины n  ), а значит общее количество разбиений равно

(2n)!= --(2n)!---= (2n− 1)!!
2nn!  2⋅4⋅...⋅2n
Ответ:

 (2n− 1)!!

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!