Закл (финал) 10 класс

Обозначим через количество способов вырезать из полоски последовательность (т.е. количество последовательностей из хотя бы нулей, перед и после которых стоят единицы). Перед каждой из них может стоять или или обозначим количество тех, перед которыми стоят через перед которыми стоят — через После каждой из последовательностей может стоять или или аналогично предыдущему предложению введём количества и Tогда

Заметим, что — это количество способов вырезать последовательность Каждый такой способ соответствует способу вырезать последовательность и наоборот, каждый способ вырезать последовательность можно единственным образом дополнить до способа вырезать последовательность Значит, количества таких способов одинаковые, и Аналогично и равняются количествам способов вырезать последовательности и соответственно. По условию, последовательность встречается наименьшее число раз, откуда Тогда, с учётом получаем что возможно только при Значит, последовательность также встречается ровно раз.