Закл (финал) 10 класс
Ошибка.
Попробуйте повторить позже
Дано натуральное число 
На кольцевой полоске бумаги написана последовательность из нулей и единиц. Для каждой
последовательности 
из 
нулей и единиц посчитали количество способов вырезать из полоски фрагмент, на котором написана 
Оказалось, что наибольшее количество 
достигается на последовательности 
а наименьшее (возможно, нулевое) — на
последовательности 
Докажите, что есть и другая последовательность из 
нулей и единиц, встречающаяся ровно 
раз.
Источники:
Подсказка 1
Обозначим через N количество способов вырезать из полоски последовательность 10...01, где нулей хотя бы n - 2. Перед каждой из них может стоять или 1, или 0. Обозначим количество тех, перед которыми стоят 1, через N_1x, перед которыми стоят 0 — через N_0x. После каждой из N последовательностей может стоять или 0, или 1; аналогично предыдущему предложению введём количества N_x0 и N_x1. Какие равенства на эти количества можно написать?
Подсказка 2
Верно, N_0x + N_1x = N = N_x0 + N_x1! Теперь стоит попробовать представить N_1x, как количество способов вырезать некоторую последовательность из условия.
Подсказка 3
Заметим, что N_1x — это количество способов вырезать последовательность 110..0, где нулей ровно n - 2, а значит, N_1x = M(поймите, почему). Аналогично можно представить остальные N-ки. Потом стоит воспользоваться равенством из подсказки 2.
Обозначим через 
количество способов вырезать из полоски последовательность 
(т.е. количество последовательностей из хотя
бы 
нулей, перед и после которых стоят единицы). Перед каждой из них может стоять или 
или 
обозначим
количество тех, перед которыми стоят 
через 
перед которыми стоят 
— через 
После каждой из 
последовательностей может стоять или 
или 
аналогично предыдущему предложению введём количества 
и 
Tогда
Заметим, что 
— это количество способов вырезать последовательность 
Каждый такой способ соответствует способу
вырезать последовательность 
и наоборот, каждый способ вырезать последовательность 
можно единственным образом
дополнить до способа вырезать последовательность 
Значит, количества таких способов одинаковые, и 
Аналогично
и 
равняются количествам способов вырезать последовательности 
и 
соответственно. По
условию, последовательность 
встречается наименьшее число раз, откуда 
Тогда, с учётом 
получаем
что возможно только при 
Значит, последовательность 
также встречается ровно 
раз.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
