ВсОШ 2022, 10 класс, задача 6
( баллов) Дано натуральное число . На кольцевой полоске бумаги написана последовательность из нулей и единиц. Для каждой последовательности из нулей и единиц посчитали количество способов вырезать из полоски фрагмент, на котором написана . Оказалось, что наибольшее количество достигается на последовательности , а наименьшее (возможно, нулевое) количество - на последовательности . Докажите, что . (А. Храбров)
Решение.
Обозначим через количество способов вырезать из полоски последовательность (т. е. количество последовательностей из хотя бы нулей, перед и после которых стоят единицы). Перед каждой из них может стоять или , или ; обозначим количество тех, перед которыми стоят , через , перед которыми стоят — через . После каждой из последовательностей может стоять или , или ; аналогично предыдущему предложению введём количества и . Тогда
Заметим, что — это количество способов вырезать последовательность . Каждый такой способ соответствует способу вырезать последовательность ; и наоборот, каждый способ вырезать последовательность можно единственным образом дополнить до способа вырезать последовательность . Значит, количества таких способов одинаковые, и . Аналогично , и равняются количествам способов вырезать последовательности , и соответственно. По условию, последовательность встречается наименьшее число раз, откуда . Тогда, с учётом , получаем , что возможно только при . Значит, последовательность также встречается ровно раз.
Замечание.
То же самое решение можно изложить на немного другом языке. Обозначим через последовательность из букв . Для слова обозначим через количество способов вырезать из полоски. Тогда для любого слова выполняется равенство .