Регион 9 класс

Первое решение.

Обозначим Назовём последовательность из натуральных чисел, любые два соседних члена которой различаются не больше, чем на интересной. Каждой интересной последовательности сопоставим разностную последовательность Все члены разностной последовательности равны или так что количество всевозможных разностных последовательностей равно

Посчитаем сначала количество всех интересных последовательностей, минимальный член которых не превосходит Рассмотрим произвольную разностную последовательность Любые две интересные последовательности, соответствующие ей, отличаются прибавлением одного и того же числа к каждому члену. Значит, среди них ровно по одной последовательности с минимальным членом, равным и Таким образом,

В учтены все последовательности, выписываемые Петей, и несколько лишних - тех, в которых не встречается Ясно, что, если в интересной последовательности встречаются как числа, большие так и меньшие то и тоже встречается. Но минимальный член каждой лишней последовательности не больше значит, и все их члены не превосходят Итак, все лишние последовательности состоят из единиц и двоек. С другой стороны, каждая последовательность из единиц и двоек является интересной, и, стало быть, лишней.

Итого, лишних последовательностей ровно а значит, искомое количество равно

______________________________________________________________________________________________________________________________________________________

Второе решение.

Назовём хорошей последовательность из натуральных чисел, в которой хотя бы раз встречается тройка, а любые два соседних члена различаются не больше, чем на Обозначим через количество хороших последовательностей длины Мы докажем индукцией по что База индукции при очевидна.

Сделаем переход от к Назовём хорошую членную последовательность отличной, если среди первых её членов встречается тройка. Откинем от каждой отличной последовательности её последний член; в каждом случае мы получим хорошую -членную последовательность. При этом, если хорошая -членная последовательность оканчивается числом то она получается таким образом из двух отличных — оканчивающихся числом или Если же оканчивается числом то она получается из трёх отличных, у которых в конце стоит или Итак, если количество -членных хороших последовательностей, оканчивающихся числом равно то количество отличных -членных последовательностей равно

Осталось посчитать количество неотличных -членных последовательностей. Ясно, что каждая из них оканчивается числом если эту тройку откинуть, получится -членная последовательность без троек. Поскольку её соседние члены отличаются не больше, чем на то либо все они больше либо все меньше

Если все члены меньше то состоит из чисел и оканчиваясь числом При этом любая такая последовательность, дополненная в конце тройкой, даст хорошую. Значит, такие последовательности получаются ровно из неотличных.

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

В итоге мы получаем, что Переход доказан.