РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 6129 Добавить в вариант

Пусть a_n  — количество перестановок (k₁, k₂, ..., k_n) чисел (1, 2, ..., n) таких, что выполнены два условия:

1)   $k_1=1;$

2)  для любого номера $i=1, 2, ..., n минус 1$ выполнено неравенство $|k_i минус k_i плюс 1| меньше или равно 2.$

Каково число a_N?

Спрятать решение

Решение.

Докажем в не сколько шагов.

Первый шаг. Докажем, что есть рекуррентное соотношение:

$a_n=a_n минус 1 плюс a_n минус 3 плюс 1.$

Возможны следующие начала перестановки:

— В последовательности (1, 2, ...,). Отбросим первую единицу, а остальные числа уменьшим на 1. То, что получилось, Удовлетворяет условиям на перестановки при $n минус 1.$ Следовательно, таких перестановок $a_n минус 1.$

— В последовательности (1, 3, 2, 4, ...,). Отбросим первые три члена перестановки ((1, 3, 2)). О стальные числа у меньшим на три. То, что получилось, удовлетворяет условиям на перестановки при $n минус 3.$ Следовательно, таких перестановок есть $a_n минус 3.$

— Есть ещё одна перестановка вида (1, 3, 5, 7, ..., 6, 4, 2). В середине  — переход с последнего нечётного числа, не превосходящего n к последнему чётному числу, не превосходящего n. Таким образом, полу чили

$a_n=a_n минус 1 плюс a_n минус 3 плюс 1 . \qquad левая круглая скобка 2 правая круглая скобка$

Второй шаг. Вычисляем начальные элементы последовательности

$\beginaligned a_1=1, \quad a_2=1, \quad a_3=2, \quad a_4=4, \quad a_5=6, \quad a_6=9, \quad a_7=14, \quad a_8=21, \quad a_9=31, a_10=46, \quad a_11=68, \quad a_12=100, \quad a_13=147, \quad a_14=216, \quad a_15=317, a_16=465, \quad a_17=682, \quad a_18=1000, \quad a_19=1466, \quad a_20=2149, \quad a_21=3150, a_22=4617, \quad a_23=6767, \quad a_24=9918, \quad a_25=14 536, \quad a_26=21 304, \quad a_27=31 223, a_28=45 760, \quad a_29=67 065, \quad a_30=98 289, \quad a_31=144 050, \quad a_32=211 116, \quad a_33=309 406, a_34=453 457, \quad a_35=664 574, \quad a_36=973 981, \quad a_37=1 427 439, \quad a_38=2 092 014, a_39=3 065 996, \quad a_40=4 493 436, \quad a_41=6 585 451, \quad a_42=9 651 448, \quad a_43=14 144 885, a_44=20 730 337, \quad a_45=30 381 786, \quad a_46=44 526 672, \quad a_47=65 257 010 . \endaligned$

Ответ: $a_41=6 585 451.$

Олимпиада Покори Воробьевы горы!, 11, 10 класс, 1 тур (отборочный), 2017 год

Классификатор: Алгебра. Рекуррентные соотношения, Комбинаторика, вероятность, статистика. Размещения, перестановки и сочетания

Спрятать решение · Помощь