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

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

Задача 1#85560

На доске написано 20-буквенное слово, состоящее только из букв А и В. Назовем крутизной слова количество способов стереть некоторые его буквы так, чтобы на доске остались четыре буквы, образующих комбинацию ABBA. Например, слово ABBAAB имеет крутизну 2 , поскольку нужную комбинацию можно получить двумя способами: АВВААВ и АВВААВ. Какова наибольшая возможная крутизна слова, выписанного на доске?

Источники: Курчатов - 2024, 11.2 (см. olimpiadakurchatov.ru)

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

Возьмём произвольное слово длины 20 и будем последовательно передвигать в нем буквы A, не уменьшая при этом крутизну слова. Ясно, что в нашем слове должно быть хотя бы две буквы B, иначе крутизна слова равна 0. Далее, предположим, что в слове между двумя буквами В есть буква А, т.е. слово имеет вид ... В. .. А. .. В ... Посмотрим, с какой стороны от буквы А больше букв А, и передвинем выделенную букву А в тот конец слова, где их меньше. Заметим, что при таком перемещении буквы А мы могли разрушить лишь слова вида ABBA и ABBA, которые давали вклад в размер крутизны исходного слова. Предположим, что мы переместили букву К налево. Тогда слова вида ABBA сохранились, а вместо слов вида ABBA, образованных буквой В слева от A  и двух букв В и буквы A  , мы получим как минимум столько же слов, которые образуются из нашей передвинутой буквы A  , двух любых букв У и любой буквы А, которая стояла в исходном слове справа от буквы А. Получается, что мы можем рассматривать только слова вида А...АВ...ВА...А. Если в левом блоке будет ℓ  букв А, а в правом − r  букв А, то крутизна такого слова равна ℓr⋅C220− (ℓ+r)  .

Заметим, что при фиксированной сумме ℓ+ r  произведение ℓr  будет максимальным, если числа ℓ  и r  отличаются не больше чем на 1: в противном случае, если, например, ℓ≥ r+ 2  , то переместим одну букву K  из левого блока в правый, и крутизна изменится на

(ℓ− 1)(r+ 1)C220−(ℓ+r)− ℓrC220−(ℓ+r) = (ℓ− r − 1)C220−(ℓ+r) > 0.

Таким образом, можно считать, что r= ℓ  или r =ℓ− 1  , причем 1≤ ℓ≤9  (иначе в нашем слове не будет или букв А, или букв В). Теперь возьмем слово, в котором r=ℓ− 1  , и заменим последнюю букву В на букву А. При такой замене крутизна слова изменится на величину

ℓ2C220−2ℓ− ℓ(ℓ− 1)C220− (2ℓ−1) = ℓ(10− ℓ)(21− 4ℓ).

Значит, при ℓ≤ 5  крутизна слова после такой замены увеличивается, а при ℓ>5− уменьшается. Аналогично, посмотрим, что произойдёт, если в слове, в котором r=ℓ  , заменить первую букву В на букву A:

ℓ(ℓ+ 1)C220−(2ℓ+1)− ℓ2C220−2ℓ = ℓ(19− 2ℓ)(9− 2ℓ).

Получается, что при ℓ <5  крутизна слова после такой замены увеличивается, а при ℓ≥ 5  - уменьшается. Значит, мы можем последовательно совершать такие замены, сводя величину ℓ  к значению 5 и увеличивая в процессе крутизну. В итоге, наибольшая крутизна будет у слова, в котором ℓ= r= 5  , и равна она 52⋅C210  .

Замечание.

Последнюю часть решения можно провести по-другому. А именно, рассмотрим крутизну слова, в котором r=ℓ  , как функцию от ℓ:S(ℓ)=  ℓ2C2
  20−2ℓ  . Вычислим ее производную: S′(ℓ)= ℓ(8ℓ2− 117ℓ+ 380) . Нас интересует натуральная точка из отрезка [1;9]  , которая наиболее близка к нулю ℓ0  этой производной. Поскольку 4,5< ℓ0 < 5  , в качестве такой точки необходимо выбрать число ℓ= 5  , что и приводит нас к примеру. Аналогичные вычисления для случая r= ℓ− 1  также дают значение ℓ =5  , но крутизна такого слова оказывается меньше.

Ответ:

 52,C2 =1125
    10

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

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

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

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

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

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

Бесплатное обучение
в Школково

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

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

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

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

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

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

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

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