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