ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65125
Темы:    [ Числовые последовательности (прочее) ]
[ Задачи с ограничениями ]
[ Индукция (прочее) ]
Сложность: 4+
Классы: 11
В корзину
Прислать комментарий

Условие

Петя хочет выписать все возможные последовательности из 100 натуральных чисел, в каждой из которых хотя бы раз встречается число 4 или 5, а любые два соседних члена различаются не больше, чем на 2. Сколько последовательностей ему придётся выписать?


Решение

  Найдём ответ для аналогичных последовательностей из n натуральных чисел.
  Первый способ. Назовём последовательность из n натуральных чисел, любые два соседних члена которой различаются не больше, чем на 2, интересной. Каждой интересной последовательности a1, a2, …, an сопоставим разностную последовательность  bi = ai+1ai  (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.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2014/2015
этап
Вариант 4
класс
Класс 11
задача
Номер 11.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .