Задача
ALG-B1-M05-P023 Последовательности с обязательным попаданием
Сколько последовательностей \(a_1,\ldots,a_n\) натуральных чисел имеют хотя бы один член \(4\) или \(5\), а любые два соседних члена отличаются не больше чем на \(2\)?
Сначала посчитайте последовательности с минимальным членом не больше \(5\), затем вычтите лишние.
Зафиксируем разности \(b_i=a_{i+1}-a_i\). Каждая разность может быть \(-2,-1,0,1,2\), всего \(5^{n-1}\) вариантов.
Для каждой разностной последовательности ровно по одной исходной последовательности имеет минимум \(1,2,3,4,5\). Поэтому последовательностей с минимумом не больше \(5\) ровно \(5^n\).
Лишние среди них — те, где нет \(4\) и \(5\). Если минимум не больше \(5\) и при шаге не больше \(2\) последовательность содержит число больше \(5\) и число меньше \(4\), то она обязана пройти через \(4\) или \(5\). Значит, лишние состоят только из \(1,2,3\). Таких \(3^n\). Ответ: \(5^n-3^n\).
Сохранена архитектура разностной последовательности и вычитания лишних случаев.