|
|
 |
Условие
Петя хочет выписать все возможные последовательности из 100 натуральных чисел, в каждой из которых хотя бы раз встречается число 4 или 5, а любые два соседних члена различаются не больше, чем на 2. Сколько последовательностей ему придётся выписать?
Решение
Найдём ответ для аналогичных последовательностей из n натуральных чисел.
Первый способ. Назовём последовательность из n натуральных чисел, любые два соседних члена которой различаются не больше, чем на 2, интересной. Каждой интересной последовательности a1, a2, …, an сопоставим разностную последовательность bi = ai+1 – ai (i = 1, 2, …, n – 1). Все члены разностной последовательности равны 0, ±1 или ±2, так что количество всевозможных разностных последовательностей равно 5n–1.
Подсчитаем сначала количество S всех интересных последовательностей, минимальный член которых не превосходит 5. Рассмотрим произвольную разностную последовательность b1, b2, …, bn–1. Любые две интересные последовательности, соответствующие ей, отличаются прибавлением одного и того же числа к каждому члену. Значит, среди них ровно по одной последовательности с минимальным членом, равным 1, 2, 3, 4 или 5. Таким образом, S = 5·5n–1 = 5n.
В S учтены все последовательности, выписываемые Петей, и несколько лишних – тех, в которых не встречается ни 4, ни 5. Ясно, что, если в интересной последовательности встречаются как числа, большие 5, так и меньшие 4, то 4 или 5 также встретится. Но минимальный член каждой лишней последовательности не больше 3, значит, и все их члены не превосходят 3. Итак, все лишние последовательности состоят из чисел 1, 2 и 3. С другой стороны, каждая последовательность из чисел 1, 2 и 3 является интересной, и, стало быть, лишней.
Итого, лишних последовательностей ровно 3n, а значит, искомое количество равно S – 3n = 5n – 3n.
Второй способ. Назовём хорошей интересную последовательность, в которой хотя бы раз встречается число 4 или 5. Обозначим через Sn количество хороших последовательностей длины n. Докажем индукцией по n, что Sn = 5n – 3n. База (n = 1) очевидна.
Шаг индукции. Рассмотрим произвольную n-членную хорошую последовательность; пусть она оканчивается числом k. Тогда к ней можно приписать любое число от k – 2 до k + 2; полученная последовательность будет хорошей, если приписываемое число натуральное. Если же оно неположительно (то есть равно 0 или –1), то после приписывания прибавим ко всем числам последовательности по 5. Полученная последовательность будет оканчиваться числом 4 или 5, а значит, будет хорошей.
Заметим, что все полученные последовательности – разные. Для последовательностей, полученных без прибавления 5, это очевидно; при этом таким образом получаются ровно все хорошие последовательности, среди первых n членов которых есть 4 или 5. Последовательности же, полученные прибавлением 5, тоже попарно различны; при этом это – ровно все хорошие последовательности, первые n членов которых больше 5, и при этом среди них встречается 9 или 10. В частности, эти последовательности отличны от описанных ранее. Итого, мы пока что построили 5Sn хороших (n+1)-членных последовательностей.
Осталось подсчитать число ещё неучтённых последовательностей. В каждой неучтённой последовательности среди первых n членов нет чисел 4, 5, 9 и 10, а последний член равен 4 или 5. Значит, либо первые n её членов – единицы, двойки и тройки, либо все они – шестёрки, семёрки или восьмёрки. Посчитаем количество первых; количество вторых считается аналогично.
Рассмотрим любую последовательность из n единиц, двоек и троек (её соседние члены автоматически отличаются максимум на 2). Если она оканчивается числом 3, то к ней можно приписать 4 или 5, получив неучтённую последовательность. Если она оканчивается числом 2, то можно приписать лишь 4; если же её последнее число – 1, то хорошую последовательность из неё получить нельзя. Значит, количество полученных неучтённых последовательностей равно 2·3n–1 + 3n–1 = 3n (и ещё столько же получаются из последовательностей с числами 6, 7 и 8).
Итак, Sn+1 = 5Sn + 2·3n = 5(5n – 3n) + 2·3n = 5n+1 – 3n+1.
Ответ
5100 – 3100.
