Тема КОМБИНАТОРИКА

Количество способов, исходов, слагаемых → .08 Рекурренты в комбинаторике и числа Фибоначчи f(n)

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Количество способов, исходов, слагаемых

Правила сложения и умножения

Счастливые билеты

Зачем делить в комбинаторике

Раскрываем скобки комбинаторными рассуждениями

Перебор случаев

Числа сочетаний (цэ изэн пока)

Метод шаров и перегородок

Рекурренты в комбинаторике и числа Фибоначчи f(n)

Числа Каталана

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#121577

На полосе из $2025$ клеток стоит топотун, который может перемещаться на одну или две клетки. Ему необходимо пройти сначала в один конец полосы, затем в другой и вернуться в начальное положение, причем на каждом из трех этапов двигаться можно только в сторону своей цели. Общее количество различных последовательностей ходов, которыми топотун может осуществить желаемое, искать не требуется. Необходимо выяснить, при каком начальном положении общее количество таких вариантов будет наибольшим.

Источники: Надежда Энергетики - 2025, 11.4(см. www.energy-hope.ru)

Подсказки к задаче

Подсказка 1

Давайте посчитаем количество способов попасть на конкретную клетку с номером k. Назовем это число Nₖ. Как его как можно проще выразить или посчитать?

Подсказка 2

Nₖ = Nₖ₋₁ + Nₖ₋₂. Теперь мы можем предположить, что изначально мы стояли на клетке с номером k, и явно записать через N количество вариантов для нашего пути.

Подсказка 3

Если всё будет посчитано правильно, то необходимо будет найти максимум у выражения Nₖ*N₂₀₂₅₋ₖ₊₁. Но сравнивать между собой такие числа сразу при всех k неудобно, значит, надо с чем-то одним. Можно выдвинуть гипотезу об ответе, какую?

Подсказка 4

Можно сравнить указанное выше число с N₂₀₂₅. Выдвигаем гипотезу о конце полосы!

Подсказка 5

Доказать неравенство можно как комбинаторно, так и по индукции, используя равенство, которое мы получили для Nₖ.

Показать ответ и решение

Пусть $N k$ — количество способов попасть на $k−$ ю по счету клетку. Туда топотун может попасть двумя способами: с клетки $k− 1$ либо $k− 2.$ Поэтому

Nk = Nk−1+ Nk−2

Если задать клетке, на которой стоит топотун, номер 1, то $N =1, 2$ $N =2. 3$

Таким образом, количество ходов задается хорошо известной последовательностью чисел Фибоначчи (начиная со второго).

Если топотун начинает с клетки с номером $k,$ то количество способов дойти до клетки с номером $L= 2025$ равно $N . L−k+1$ Количество способов дойти от клетки с номером $L= 2025$ до первой клетки (пройти всю полосу) составляет $NL,$ а количество способов вернуться с клетки номер один на клетку с номером $k$ равно $Nk.$ Общее количество вариантов есть $NL−k+1⋅NL ⋅Nk.$ Если же движение начинается из конца полосы, то общее количество вариантов есть $NL ⋅NL.$

Таким образом, необходимо найти максимум по параметру $k$ выражения

Nk⋅NL−k+1

(для $L = 2025$ ) и сравнить его с $N . L$

Если провести расчеты при небольших значениях $L,$ то можно выдвинуть гипотезу, что

Nk⋅NL−k+1 < NL

1 вариант. Рассмотрим выражения $N ⋅N k L−k+1$ и $N L$ как количество способов передвинуться по полосе. Первое из них соответствует количеству способов переместиться на $L −$ ю клетку вправо, но с обязательным посещением

клетки с номером $k.$ Второе $(N ) L$ есть общее количество способов переместиться на такое же количество клеток, которое включает в себя как варианты с посещением клетки с номером $k,$ так и варианты с перепрыгиванием этой клетки.

Следовательно, $NL > Nk ⋅NL −k+1.$

2 вариант. Перепишем доказываемую формулу в виде

Nk ⋅Nm <Nk+m −1

и докажем ее индукцией по $k$ при фиксированном $m.$

Базу проверим для $k =2.$ $N2 ⋅Nm =1⋅Nm < N2+m− 1.$

Теперь рассмотрим значение параметра $k+ 1$ в предположении, что для всех предыдущих значений $k$ неравенство верно.

N(k+1)+m−1 = Nk+m−1 +Nk+m −2 > Nk⋅Nm + Nk−1⋅Nm =(Nk +Nk−1)Nm = Nk+1⋅Nm

Таким образом, максимальное количество вариантов будет при начале движения из любого конца полосы.

Ответ:

При начале движения из любого конца полосы

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#126198

Найдите количество перестановок ( $a ,a,...,a 1 2 10$ ) набора чисел $(1,2,...,10),$ таких, что $a ≤2a ≤ ...≤ 10a . 1 2 10$

Источники: Курчатов - 2025, 10.5 ( см. olimpiadakurchatov.ru)

Подсказки к задаче

Подсказка 1

Для решения данной задачи необходимо доказать, что количество перестановок чисел a₁; a₂;...; aₙ равно F(n + 1), где F(n) — число Фибоначчи с номером n.

Подсказка 2

Будем доказывать это утверждение по индукции. Для n = 1 и n = 2 можно проверить утверждение перебором (получается, база индукции уже есть!). Для того, чтобы доказать данное утверждение для больших n будем рассматривать такой индекс k, что k-ый член последовательности равен n. Посмотрим тогда внимательно на отрезок [k + 1;n] и подумаем, какие числа могут на нём лежать.

Показать ответ и решение

Докажем следующее утверждение: количество перестановок $a ,a ,...,a 1 2 n$ чисел $1,2,...,n$ таких, что $a ≤ 2a ≤ ...≤ na , 1 2 n$ равно $F , n+1$ где $Fn$ — $n$ -е число Фибоначчи $(F1 =F2 =1,$ $Fk+1 = Fk+ Fk−1).$ Отсюда будет следовать, что ответом является число $F11 = 89.$

Обозначим через $Pn$ количество искомых перестановок длины $n.$ Заметим, что $P1 = 1,$ $P2 = 2.$ Докажем, что $Pn+1 = Pn+ Pn− 1$ при $n ≥ 2.$ Для этого поймем, на какой позиции может стоять в нашей перестановке число $n.$

Пусть $k$ — такой индекс, что $ak = n.$ При $k= n$ мы получаем $an = n,$ количество таких перестановок равно $Pn−1.$ При $k =n − 1$ имеем $nan ≥ n(n − 1),$ тогда $an ≥ n− 1.$ Но $an ⁄= n,$ поэтому $an = n− 1,$ количество перестановок равно $Pn−2.$

Предположим, что существует такая перестановка, что $ak =n$ при $k ≤n − 2.$ Для каждого $i∈(k,n)$ имеем

kn = kak ≤iai < nai,

поэтому $ai ≥ k+ 1.$ Кроме того,

nan ≥ (n − 1)an−1 ≥(n− 1)(k+ 1)

Из этого следует

an ≥ k+1

Получается, что все числа $ak,ak+1,...,an$ лежат на отрезке $[k+1;n].$ Но на этом отрезке лишь $n− k$ чисел, значит, мы получили противоречие.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 3#80741

Есть $4n$ отрезков длины $x 1$ , $x 2$ , …, $x 4n$ , где $x = 1 1$ , $x =2 2$ , а при $k> 2$ выполнено $x = x + x k k−1 k−2$ . Сколькими способами эти отрезки можно разбить на четвёрки так, чтобы из отрезков каждой четвёрки можно было составить четырёхугольник?

Источники: Высшая проба - 2024, 11.4 (см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

Подумайте, при каком условии из четырех отрезков можно составить четырехугольник. Вспомните аналогичное условие для треугольников.

Подсказка 2

Да, из отрезком a < b < c < d можно составить четырёхугольник <=> a+b+c > d, попробуйте рассмотреть произвольную четвёрку, которая образует четырёхугольник и расписать свойство x_k = x_{k-1} + x_{k-2} более подробно, т.е. для x_{k-1} применить его же и посмотреть чему тогда должно быть равно c и b.

Подсказка 3

Верно, если d = x_{k}, то b = x_{k-2}, c = x_{k-1}, иначе четырёхугольник не построится. Теперь задача свелась к подсчету количества способов выбрать n пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной тройки.

Подсказка 4

Введем понятие "хорошей" последовательности, состоящей из 2n чисел, в которой каждое из чисел 1, ..., n участвует ровно два раза. Как мы можем восстановить способ разбиения последовательности отрезков по хорошей последовательности? Может мы можем первому вхождению числа в "хорошую" последовательность сопоставить число, а второму - тройку?

Подсказка 5

Теперь давайте подсчитаем количество хороших последовательностей. Сколькими способами можно выбрать индексы для двух единиц? А сколько тогда останется возможных индексов для двух двоек? А сколько всего получится способов сопоставить каждому числу 2 индекса?

Подсказка 6

А не посчитали ли мы что-либо несколько раз? Меняет ли перестановка чисел в "хорошей" последовательности набор отрезков?

Показать ответ и решение

Из отрезков $a< b< c< d$ можно сложить четырехугольник тогда и только тогда, когда $a+ b+ c> d$ . Рассмотрим четверку $xs < xi < xj < xk$ , заметим, что $xk =xk−1+ xk−2 = 2xk−2 +xk−3 > xk−2+xk−3+ xk−4$ , следовательно, $xj = xk−1$ , иначе проверяемое неравенство не выполнено. Аналогично, можно показать, что $xi =xk−2$ .

Назовем последовательность $4n {xi}i=1$ интересной. Таким образом, необходимо посчитать количество способов выбрать в интересной последовательности $n$ пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной тройки.

Рассмотрим последовательность, состоящую из $2n$ чисел, в котором каждое из чисел $1,...,n$ участвуют ровно два раза и назовем ее хорошей. Восстановим по хорошей последовательности способ разбиения интересной последовательности. На первом шаге рассмотрим первое число в каждой из последовательности. На каждом следующем шаге, если рассматриваемое число в хорошей последовательности встречается впервые, то ставим ему в соответствие рассматриваемое число в интересной последовательно, после чего рассматриваем следующий числа в каждой из последовательностей. Если рассматриваемое число в хорошей последовательности встречается во второй раз, то ставим ему в соответствие тройку из рассматриваемого элемента в интересной последовательности и двух элементов, идущих после него. Таким образом, к концу процесса, каждому первому вхождению числа в хорошей последовательности стоит в соответствие один элемент интересной последовательности, а каждому второму тройка подряд идущих элементов интересной последовательности.

Посчитаем количество хороших последовательностей. Существует $C22n$ способов выбрать индексы двум единичкам, после этого останется $2n− 2$ возможных индекса, следовательно, существует ровно $C22n−2$ способов выбрать индексы для двух двоек. Продолжая ставить каждому из чисел в соответствие два индекса, получим что общее количество способов сделать это, равно $(2n)!∕2n$ . Осталось заметить, что каждая перестановка чисел в хорошей последовательности не меняет набор разбиение интересной последовательности, следовательно, каждое разбиение было посчитано $n!$ раз (количество перестановок длины $n$ ), а значит общее количество разбиений равно

(2n)!= --(2n)!---= (2n− 1)!! 2nn! 2⋅4⋅...⋅2n

Ответ:

$(2n− 1)!!$

Ошибка.
Попробуйте повторить позже

Задача 4#102018

Дан прямоугольник $2×n.$ Сколькими способами его можно разрезать на доминошки, состоящие из $2$ клеток?

Подсказки к задаче

Подсказка 1

Давайте предположим, что мы знаем, сколькими способами можно замостить прямоугольник 2×n. Можно ли зная это, вычислить число способ замещения прямоугольника 2×(n+1)?

Подсказка 2

Чтобы ответить на вопрос из подсказки 1, обратите внимание на крайний столбец прямоугольника 2×(n+1). Как эти клетки могут быть покрыты?

Подсказка 3

Правильно, либо одним прямоугольником, либо двумя. В первом случае остаётся пустой прямоугольник 2×n, а во втором 2×(n-1). Какой вывод можно сделать?

Показать ответ и решение

Обозначим за $A n$ количество способов разрезать прямоугольник $2× n$ на доминошки. Давайте по индукции докажем, что $A = F . n n+1$ Для $n= 1,2$ очевидно. Теперь переход. Посмотрим на левую верхнюю крайнею клетку прямоугольника $2 ×n.$ Ее содержит вертикальная или горизонтальная доминошка. Если доминошка вертикальная, то остается только разрезать прямоугольник $2×(n− 1),$ а по предположению способов это сделать равно $Fn.$ Если же доминошка будет горизонтальной, то и под ней должна быть горизонтальная, а значит, останется только разрезать прямоугольник $2× (n− 2),$ а опять же по предположению количество способов это сделать равно $Fn−1.$ Следовательно, количество способов разрезать $2×n$ равно $Fn−1+ Fn = Fn+1,$ что и требовалось.

Ответ:

$F n+1$ число Фибоначчи

Ошибка.
Попробуйте повторить позже

Задача 5#102021

Садовник, привив черенок редкого растения, оставляет его расти два года, а затем ежегодно берет от него по три черенка. С каждым новым черенком он поступает аналогично. Сколько растений будет у садовника на седьмом году роста первоначального растения?

Подсказки к задаче

Подсказка

Тут стоит ввести последовательность. Пусть X_n - количество растений в n-й день. Как тогда связано X_n с предыдущими членами?

Показать ответ и решение

Обозначим $X n$ — число растений на $n−$ й год. Ясно, что $X = 0 0$ и $X = 1. 1$ Для $n ≥2$ имеет место соотношение $X = X + 3X n n−1 n−2$ (три черенка от растений, который растут хотя бы $2$ года и все имеющиеся растений за прошлые года). Характеристическое уравнение линейного рекуррентного соотношения имеет вид $2 q − q− 3= 0,$ откуда $1±√13- q = 2 .$ Таким образом,

(1 − √13)n ( 1+ √13)n Xn =A ---2-- + B --2---

Из начальных условий $A +B = 0$ и $(1− √13)A+ (1 +√13)B =2.$ Поскольку $A= −B,$ то $− 2√13A = 2,$ то есть $A = −√1-. 13$ Итак,

1 ((1+ √13)n (1− √13)n) Xn = √13 ---2-- − ---2--

Подставлять сюда $7$ и считать, что получится, очень не хочется, так что удобнее получить ответ через рекурренту.

Ответ:

$97$

Ошибка.
Попробуйте повторить позже

Задача 6#102023

Обозначим через $A n$ количество несамопересекающихся ломаных из $n$ звеньев, начинающихся в точке $(0,0),$ каждое звено которых совпадает с одним из векторов $r= (1,0),$ $u =(0,1),$ $d= (0,−1).$ Выразите $An$ через $An−1$ и $An−2.$

Подсказки к задаче

Подсказка 1

Давайте рассмотрим ломаную из n звеньев и поймём, сколько ломаных с n+1 звеном можно получить. Если ломаная заканчивается звеном вверх или вниз, то две. Если звеном вперёд - то три.

Подсказка 2

Зная количество ломаных, оканчивающихся звеном вверх, вниз, вперёд, мы сможем найти связь между A_(n), A_(n-1), A_(n-2).

Подсказка 3

Тогда давайте введём вспомогательные поcледовательности R_(n) и U_(n), где первая - количество ломаных из n звеньев с последним звеном вверх (количество ломаных с последним звеном вниз такое же), вторая - с последним звеном вперёд. Поработайте с ними и A_(n).

Показать ответ и решение

Разобьём ломаные на три вида, обозначим их соответствующими буквами:

1.: $R n$ — количество ломаных из $n$ звеньев, в которых последний шаг направо.
2.: $Ln$ — количество ломаных из $n$ звеньев, в которых последний шаг налево.
3.: $Un$ — количество ломаных из $n$ звеньев, в которых последний шаг вверх.

В силу симметрии ясно, что $Ln = Rn.$ Также единственная возможность для самопересечения — это после шага направо пойти налево, поскольку мы не можем опуститься вниз. Тогда напишем рекуррентное соотношение:

Rn = Un−1+ Rn−1, Un = Un−1+ 2Rn−1

А поскольку $Ln = Rn$

An =Un +2Rn, Un+1 = An

Тогда

An = Un+ 2Rn = Un−1+ 2Rn−1+ 2(Un−1+ Rn−1)=

= 2An− 1+Un−1 =2An−1 +An−2

Получаем ответ $An =2An−1+ An−2.$

Ответ:

$A = 2A +A n n− 1 n− 2$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#102024

Некоторые клетки доски $2× n$ красятся в красный цвет так, чтобы ни одна красная клетка не имела соседей по стороне того же цвета. Обозначим через $An$ количество таких раскрасок с четным числом красных клеток, через $Bn$ — с нечетным числом. Чему может быть равно $An − Bn?$

Подсказки к задаче

Подсказка 1

Глобально мы хотим выразить A_(n) через члены последовательностей A и B с меньшими индексами. Аналогично мы хотим поступить с B_(n) в надежде, что разность этих выражений будет красивым числом.

Подсказка 2

Как это сделать? Пусть закрашено четное число клеток. Давайте посмотрим на крайний столбец доски 2×n. Как выразить A_(n) через члены A и B с меньшими индексами, если клетки этого столбца не закрашены?

Подсказка 3

Если же закрашена одна клетка, то тогда придется рассмотреть случаи, как закрашены клетки в предпоследнем столбце и так дальше.

Показать ответ и решение

Разделим доски на два типа: обычные $F n$ — доски $2×n$ и $G n$ — доски $2× n$ с удаленной угловой клеткой. Дополнительно найдем $Cn$ и $Dn$ — количества правильных раскрасок $Gn$ в четное и нечетное число цветов. Клетки будем нумеровать буквой $a$ или $b,$ соответствующей строке и числами от $1$ до $n$ — столбцы. Множество таких раскрасок разбивается на три подмножества: $an$ закрашена, $bn$ закрашена и ни одна из клеток $an,$ $bn$ не закрашена. Если закрашена $an,$ то $an−1$ и $bn$ не закрашены. Среди остальных клеток правильным образом должно быть закрашено нечетное количество, таким образом, в первом и втором случаях число раскрасок равно $Dn−1.$ Если же обе клетки $an,bn$ не закрашены, то остальные должны быть раскрашены в четное количество, то есть в $An−1.$ Таким образом, $An =An −1+2Dn−1.$ Аналогично

Bn =Bn−1 +2Cn−1

Cn = An−1+ Dn−1

Dn = Bn−1+ Cn−1

Пусть $Pn = An− Bn$ и $Qn =Cn − Dn.$ Тогда $Pn = Pn−1− 2Qn−1,$ $Qn = Pn−1− Qn−1.$ Ясно, что $P1 = −1$ и $Q1 = 0.$ Находим последовательно первые несколько членов ${Pn}$ и ${Qn}:$ $(−1,−1,1,1,−1)$ и $(0,−1,0,1,0).$ Далее последовательности периодичны. Таким образом, $Pn ∈ {±1}.$

Ответ:

$±1$

Ошибка.
Попробуйте повторить позже

Задача 8#102025

Сколько имеется $2016$ -значных чисел, у которых все цифры принадлежат множеству ${1,2,3,4,5}$ и любые две соседние цифры отличаются на $1?$

Подсказки к задаче

Подсказка 1

Неочевидно, как сразу выразить интересующее нас количество рекуррентной формулой. Зато, если ввести свою переменную на каждый вариант последней цифры, несложно понять, что происходит при приписывании ещё одной цифры.

Подсказка 2

Полезно посмотреть на начало последовательностей. Это позволяет заметить, как выглядят числа на каждом чётном шаге рекурсии. Осталось только доказать предположение по индукции.

Показать ответ и решение

Разобьём числа на пять видов по последней цифре, обозначим их соответствующими символами:

1.: $Nn 1$ — количество чисел из $n$ знаков, которые кончаются на $1.$
2.: $n N 2$ — количество чисел из $n$ знаков, которые кончаются на $2.$
3.: $n N 3$ — количество чисел из $n$ знаков, которые кончаются на $3.$
4.: $n N 4$ — количество чисел из $n$ знаков, которые кончаются на $4.$
5.: $Nn5$ — количество чисел из $n$ знаков, которые кончаются на $5.$

Тогда напишем рекуррентные соотношения:

(|| Nn+1= Nn ||||| 1n+1 2n n ||{ N2 = N1 +N 3 || Nn3+1= Nn2 +Nn4 ||||| Nn4+1= Nn3 +Nn5 ||( Nn+1= Nn 5 4

Ясно, что $Nn = Nn 1 5$ и $Nn = Nn 2 4$ (например, можно построить биекцию, заменив $1$ на $5$ и $2$ на $4).$ Тогда давайте по индукции доказывать, что при $n= 2k$ — $Nn = Nn =3k−1 1 5$ и $Nn =Nn = Nn = 2⋅3k−1. 2 3 4$ База очевидна, двузначные числа $21,$ $12,$ $32,$ $23,$ $43,$ $34,$ $54,$ $45.$ Теперь переход с помощью рекурренты:

(||Nn+1 = 2⋅3k−1 ||||| 1n+1 k−1 |||||N 2 = 3⋅3 {Nn+31 = 4⋅3k−1 ||||Nn+12 = 3⋅3k−1 =3k |||||Nn+2 = 6⋅3k−1 =2 ⋅3k |||( 2n+1 k−1 k N 3 = 6⋅3 =2 ⋅3

Теперь у нас спрашивают про $n =2016= 1008⋅2.$ Получаем

(| 2016 1007 |||||N1 = 3 |||{N22016= 2⋅31007 |N23016= 2⋅31007 |||||N2016= 2⋅31007 |||( 42016 1007 N5 = 3

Значит, ответ $1007 8⋅3 .$

Ответ:

$8⋅31007$

Ошибка.
Попробуйте повторить позже

Задача 9#102027

Дима и Саша занимаются двумя на первый взгляд совершенно разными делами. У Димы есть фигура “хромой король” — она умеет ходить на 1 клетку вверх или вправо, а также на $1$ клетку по диагонали вправо-вверх. Пусть $A$ — количество путей хромого короля по доске $n ×n$ из левого нижнего угла в правый верхний, которые никогда не поднимаются выше главной диагонали.

А у Саши есть бумажный квадрат $n× n$ и резак, которым он может проводить горизонтальные или вертикальные разрезы “от края до края”. Саша отметил $n − 1$ узлов клеток, лежащих внутри квадрата на его главной диагонали, и каждый очередной разрез делает по одному из отмеченных узлов, по которому еще разрез не проводился (разрез проводится от края до края того куска бумаги, на котором расположен выбранный на данном ходу узел). Пусть $B$ — количество способов так разрезать квадрат (способы отличающиеся только порядком разрезов считаются одинаковыми). Докажите, что $A = B.$

На рисунках изображены примеры всевозможных способов при $n= 3.$

$PIC$

Подсказки к задаче

Подсказка 1

Тут не нужно в явном виде считать формулу n-го члена для каждой конструкции. Достаточно доказать, что количество способов описывается одинаковым рекуррентные соотношением, в котором первые члены равны.

Подсказка 2

В первом соотношении стоит ввести последовательность a_n - количество способов попасть в n-ю клетку на главной диагонали.

Подсказка 3

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

Показать доказательство

Докажем, что оба количества способов удовлетворяют одному и тому же рекуррентному соотношению

n∑−1 a1 =1, a2 =2, an =an−1+ akan− k k=1

Для хромого короля рассмотрим первый момент на пути (не считая стартовой клетки), когда он попал на главную диагональ. Если это произошло первым же ходом, то мы получаем $a n−1$ способов. Если нет, то первый ход был направо, и далее есть $n$ вариантов, в зависимости от того, в каком столбце впервые король попал на главную диагональ. Если он туда попал в $k+1$ по счету слева столбце, то сделал он это ходом вверх, и до этой клетки добраться было $ak$ способов. С этой клетки до правой-верхней есть $an−k$ способов добраться. Так и получается искомое рекуррентное соотношение.

Для разрезов пронумеруем отмеченные узлы слева направо от $1$ до $n − 1.$ Пусть $k$ -й узел это наименьший узел, по которому разрез проходит от края до края исходного квадрата. Не умаляя общности, он проходит по вертикали. Если этот разрез прошел по $1$ узлу, то остается $an−1$ способов проделать разрезы дальше. Если по $(n− 1)$ -му, то $an−1∕2$ способов (потому что направление следующего разреза предопределено, а значит, вдвое меньше количества всех возможных способов провести дальнейшие разрезы). Если же по какому-то промежуточному узлу $2 ≤k ≤n − 2,$ то есть $ak∕2$ способов провести разрезы слева и $an−k$ способов провести разрезы справа. Не забудем умножить итоговую сумму на $2,$ поскольку первый разрез можно было провести в любом из двух направлений, и получим следующее соотношение:

n−2 an = 2(an−1+ an−1∕2+ ∑ akan−k) k=2

что с учетом $a1 =1$ упрощается до искомого соотношения.

Ошибка.
Попробуйте повторить позже

Задача 10#103200

Сколько $n$ -буквенных слов ( $n$ — натуральное) можно составить из букв $a$ и $b$ так, чтобы после каждой буквы $a$ стояла хотя бы одна буква $b?$ (Букве $a$ разрешается быть последней).

Показать ответ и решение

Пусть подходящих слов длины $n− S . n$ Тогда рассмотрим последнюю букву в нашем слове. Если она $a,$ то перед ней обязательно $b,$ значит, слов, кончающихся на $a− Sn−2.$ Слов, кончающихся на $b− Sn−1.$ То есть $Sn = Sn−2+ Sn−1.$ Значит, наш ответ совпадает с числами Фибоначчи. Для $n= 1$ слова $2,$ для $n =2$ слова $3.$ Значит, ответ $Fn+2.$

Ответ:

$F n+2$

Ошибка.
Попробуйте повторить позже

Задача 11#74089

Сколько семибуквенных слов можно составить из букв $a$ и $b$ так, чтобы после каждой буквы $a$ стояла хотя бы одна буква $b?$ (Букве $a$ разрешается быть последней.)

Подсказки к задаче

Подсказка 1

Предположим, что есть 6 буквенное слово, которое подходит под условие, как из него получить подходящее 7 буквенное слово?

Подсказка 2

Верно, можно просто дописать в конец букву «b»! Конечно, возможно, букву a тоже можно добавить, но иногда этого делать нельзя. В каком случае это делать нельзя и как всё таки посчитать все слова, которые оканчиваются на «a»?

Подсказка 3

Да, если последняя буква в 6 буквенном слове — «a», то еще одну «a» ставить в конец нельзя! Поэтому, попробуем идти теперь от «хорошего» 5 буквенного слова. Какую комбинацию можно добавить в конец, чтобы условие было верным для полученного слова?

Подсказка 4

Да, можно в конец 5 буквенного слова дописать «ba». То есть, мы умеем считать число слов длины n через количество слов длины n-1 и n-2! Поэтому, остаётся выяснить сколько есть подходящих слов длины 0 и 1, а дальше дойти до слов длины

Показать ответ и решение

Заметим, если наше слово заканчивается на $a,$ то перед $a$ стоит $b.$ Пусть нужных нам слов длины $n$ — $S . n$ Чтобы получить нужное нам слово длины $n,$ мы или к любому слову длины $n − 1$ добавим в конце $b$ (таким образом получим все возможные слова с окончанием $b$ ), или к любому слову длины $n− 2$ добавим в конце $ba$ (таким образом получим все возможные слова с окончанием $a$ ). Получается, что $Sn = Sn−1+ Sn−2.$ $S0 =1,S1 = 2,$ значит, $S7$ равно девятому числу Фибоначчи, что равно $34.$

Ответ:

$34$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#35431

Максим поднимается по лестнице из двенадцати ступенек. Ступив на первую ступеньку, далее он может шагать вверх либо на одну ступеньку, либо на две. Сколькими способами Максим сможет подняться по лестнице?

Показать ответ и решение

Количество способов подняться на лестницу из $n$ ступенек, находясь у ее подножья и соблюдая условия задачи, обозначим через $f n$ . На первую и на вторую ступеньки Максим может попасть единственным способом, поэтому $f1 = 1,f2 = 1$ .

Пусть Максим поднимается по лестнице, в которой $n +2$ ступеньки. Если его первый шаг был на две ступеньки (с первой на третью), то ему останется преодолеть $n$ ступенек и количество способов закончить подъем равно $fn$ .

Если же первый шаг был на одну ступеньку, то количество способов закончить подъем равно $fn+1$ .

Значит, $fn+2 =fn+ fn+1$ . Это равенство позволяет, зная $f1$ и $f2$ , последовательно вычислить значение $fn$ для любого натурального $n$ . В нашем случае $f3 = 2,f4 = 3,f5 = 5$ , $f6 = 8,f7 = 13,f8 = 21,f9 = 34,f10 = 55,f11 = 89,f12 =144$ .

Ответ: 144

Ошибка.
Попробуйте повторить позже

Задача 13#74947

В школе математики и программирования лестница с первого этажа на второй этаж состоит из двух пролетов, состоящих из 8 и 9 ступенек. Сколькими способами десятиклассник Вася может спуститься по ней, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки?

Источники: САММАТ-2022, 11.3 (см. sammat.samgtu.ru)

Подсказки к задаче

Подсказка 1

На сколько изменится количество способов, если Вася будет стоять на одну ступенью ниже? А на две? Попробуем задать количество способов рекуррентно)

Подсказка 2

Заметим, что количество способов при k ступеньках равно сумме количеств способов при k-1, k-2, k-3 ступеньках. Осталось лишь начать считать "снизу"!

Показать ответ и решение

Обозначим число способов спуститься по лестнице из $k$ ступенек за $N k$ . По условию Вася может шагать на одну, две или три ступеньки вниз с текущей, поэтому $Nk =Nk− 1+Nk−2 +Nk−3.$ Учитывая, что $N0 = 1$ (у Васи один способ — стоять на месте), $N1 = 1,N2 =2,$ последовательно находим

N3 = 2+ 1+1 =4

N4 = 4+ 2+1 =7

N5 = 7+4+ 2= 13

N6 = 13+ 7+4 =24

N7 = 24+13+ 7= 44

N8 =44+ 24+13 =81

N9 = 81+44+ 24= 149

Так как на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, нужно перемножить полученные числа вариантов $N8$ и $N9,$ так что искомое число вариантов равно $81⋅149 =12069.$

Ответ: 12069

Ошибка.
Попробуйте повторить позже

Задача 14#78846

Блоха Кузя может совершать прыжки из каждой вершины правильного тетраэдра $ABCD$ в три соседние вершины, причем выбор этих вершин случайный и равновозможный. Прыгать Кузя начала из вершины A и, совершив 2020 прыжков, опять оказалась в той же вершине. С какой вероятностью это могло произойти?

Источники: Росатом - 2020, отборочный этап (см. olymp.mephi.ru)

Подсказки к задаче

Подсказка 1

2020 прыжков довольно много, давайте рассмотрим конкретный прыжок на каком-то k-ом шаге, с какой вероятностью она сможет попасть в A?

Подсказка 2

Верно, есть 2 случая: она в самой вершине A, тогда за 1 шаг ничего не получится или не в A, тогда вероятность равна 1/3, а можем ли мы как-то обобщить наш результат, получить такую формулу, чтобы по кол-ву шагов знать вероятность попадания в A на следующем шаге?

Подсказка 3

Давайте начнём строить нашу последовательность p_n, где p_n - вероятность попасть в A на n-ом шаге. Очевидно, что p_0 = 1 (мы стартуем из A), p_1 = 0 (мы точно ушли из A), p_2 = 1/3 (пойти в обратном направлении), p_3 = (1-p_2)*1/3 = 1/3 - 1/9 (не пойти в обратном направлении на шаге 2, но вернуться в точку A на шаге 3). Аналогично, выписывая последующие члены последовательности получите предположение об общей формуле

Подсказка 4

pₙ = 1/3 - 1/9 + 1/27 + ... + (-1)ⁿ/(3ⁿ⁻¹), давайте докажем её по индукции! (тут нужно брать n = 2 для базы)

Показать ответ и решение

Рассмотрим некоторый промежуточный шаг в движении Кузи. Если она на этом шаге находится в точке $A$ , то вероятность попасть в $A$ на следующем шаге равна нулю. Если же она находится в любой из оставшихся точек $B,C$ или $D$ ,то вероятность попасть в $A$ на следующем шаге равна $1 3$ , так как из каждой такой точки есть три равновозможных пути, только один из которых приводит в $A$ . Пусть $pk$ — вероятность того, что на $k−$ ом шаге блоха находится в точке $A$ . Соответственно не в точке $A$ она находится с вероятностью $1− pk$ . Тогда на следующем шаге она окажется в $A$ с вероятностью

1 1 pk+1 = (1− pk)⋅3 +0 ⋅pk = (1− pk)⋅3

Таким образом, $p0 = 1$ (так как изначально блоха в точке $A$ ), $p1 =0, p2 = 13,$

( ) p3 = 1− 1 ⋅ 1= 1 − 1, ..., 3 3 3 9

Можно заметить закономерность и заключить при $n≥ 2$

p = 1− 1 +-1 ⋅⋅⋅+ (−-1)n- n 3 9 27 3n−1

Видим, что $p n$ представляет собой сумму членов геометрической прогрессии со знаменателем равным $− 1. 3$ Следовательно,

1− (−1)n−1 n−1 n pn = 1⋅----3n1−1-= 3---+n(−−11) 3 1 +3 4⋅3

32019+-1 P(A)= p2020 = 4⋅32019

Замечание. Чтобы решение было более обоснованным, формулу для $pn$ при $n≥ 2$ можно доказать методом математической индукции.

База:

(−1)2 1 p2 = 32−-1 = 3

Шаг: пусть формула верна для $n= k$ , то есть

k pk = 1− 1 +-1 ⋅⋅⋅+ (−k1)−1 3 9 27 3

Тогда

1 ( 1 1 1- (−1)k) 1 pk+1 = (1− pk)⋅3 = 1 −3 + 9 − 27 + ⋅⋅⋅− 3k−1 ⋅3 =

k+1 k+1 = 1− -1- +-1- − -1--+⋅⋅⋅+ (−1k−)1- = 1− 1 + 1-⋅⋅⋅+ (−-1)k-- 3 3⋅3 9 ⋅3 27 ⋅3 3 ⋅3 3 9 27 3

то есть формула верна и для $n= k+ 1$ . А значит, верна и при любых $n ≥2.$

Ответ:

$32019-+1 4⋅32019$

Ошибка.
Попробуйте повторить позже

Задача 15#102398

В алфавите жителей сказочной планеты АБ2020 всего две буквы: буква А и буква Б. Все слова начинаются на букву А и заканчиваются тоже на букву А. В любом слове буква А не может соседствовать с другой буквой А. Также не может идти подряд больше, чем $2$ буквы Б. Например, слова АББА, АБАБАБА, АББАБАББА являются допустимыми, а слова АББАБ, АБААБА, АБАБББА — нет. Сколько $20$ -буквенных слов в словаре этой планеты?

Источники: ПВГ - 2020, 11.5 (pvg.mk.ru))

Подсказки к задаче

Подсказка 1

Ого, нам нужно сделать какие-то выводы о словах, в которых аж 20 букв.. Попробовать выписать их все — не вариант, ведь их может быть слишком много. Давайте тогда в целом посмотрим на словарь инопланетян. Сколько там совсем маленьких слов, состоящих из одной, двух, трёх, четырёх букв?

Подсказка 2

Было бы здорово найти какую-нибудь формулу для количества слов, состоящих из n букв. Мы знаем, чему равно это количество для маленьких n, поэтому можем попробовать найти рекуррентное соотношение. Что мы можем сказать про слово из n букв?

Подсказка 3

То, что в нём соблюдаются все условия на то, чтобы строка была словом, а значит, оно заканчивается на букву А. Тогда предпоследняя буква — это Б. А что слоит перед Б? Рассмотрите несколько случаев и поймите, как устроено слово из n букв.

Подсказка 4

Получается, слово из n букв — это либо слово из n-2 букв, к которому приписали БА, либо слово из n-3 букв, к которому приписали ББА. Теперь не трудно написать рекуррентную формулу и найти искомое количество:)

Показать ответ и решение

Пусть $W i$ — это количество слов инопланетят, состоящих из $i$ букв.

Заметим, что единственное однобуквенное слово — это слово А. Двухбуквенных слов вообще нет, так как первая и последняя, то есть первая и вторая буквы — это А, но тогда две буквы А стоят рядом, что противоречит определению инопланетного слова. Трёхбуквенное слово тоже только одно — АБА. И четырёхбуквенное слово единственно — АББА. Таким образом,

W1 =1,W2 =0,W3 =1,W4 =1

Рассмотрим теперь какое-нибудь слово $ω$ длины $n,$ где $n >4.$ Его последняя буква — это точно буква А, так как каждое слово начинается и заканчивается буквой А. Предпоследняя буква — это Б, так как две буквы А не могут идти подряд. Есть два варианта, какой может быть буква перед Б, то есть предпредпоследняя буква слова $ω$ :

1) Это буква А. Тогда слово $ω$ имеет вид А...АБА. Рассмотрим строку из первых $n− 2$ букв этого слова. Она начинается и заканчивается на А, а так же в ней нет двух букв А подряд или трёх букв Б подряд, так как иначе $ω$ не было бы словом. А значит эта строка сама является словом.

2) Это буква Б. Тогда перед этой буквой Б стоит буква А, там как три буквы Б не могут идти подряд, и слово $ω$ имеет вид А...АББА. Аналогично случаю 1, строка, образованная первыми $n− 3$ буквами $ω$ будет являться словом.

Получается, что слово $ω$ могло быть получено либо приписыванием строки БА в конец какого-нибудь слова из $n − 2$ букв, либо приписыванием строки ББА в конец какого-нибудь слова из $n− 3$ букв. При этом, приписав в конец каждого из $Wn−2$ слов длины $n− 2$ строку БА, мы получим $Wn−2$ различных слов длины $n.$ Аналогично, приписав в конец каждого из $Wn −3$ слов длины $n − 3$ строку ББА, мы получим $Wn −3$ различных слов длины $n.$ Отсюда,

Wn = Wn−2+ Wn−3

Пользуясь этой формулой, найдем $Wi$ для $i= 5,...,20.$


$W1$	$W2$	$W3$	$W4$	$W5$	$W6$	$W7$	$W8$	$W9$	$W10$

$1$	$0$	$1$	$1$	$1$	$2$	$2$	$3$	$4$	$5$

Итак, в словаре сказочной планеты 86 20-буквенных слов.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 16#95761

Заведующая библиотекой, увидев, что $11$ томов «Малой энциклопедии козлов» стоят в беспорядке, указала на это библиотекарю. Тот в ответ заявил: «Беспорядок — небольшой, так как каждый том стоит либо на своем месте, либо на соседнем». Сколькими способами можно расставить тома энциклопедии в соответствии с этим условием?

Источники: Лига открытий - 2018

Показать ответ и решение

Пусть $F n$ — количество способов расставить ровно $n$ томов в небольшом беспорядке. Рассмотрим первый том. Если он стоит на своем месте, то остальные тома можно расставить $Fn−1$ способами. Если первый том стоит на втором месте, то на первом месте может стоять только второй том, а остальные расставляются $Fn−2$ способами. Итого, мы получаем, что $Fn = Fn−1+ Fn−2.$ Также $F1 =1$ и $F2 = 2.$ Откуда $F11 = 144.$

Ответ:

$144$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#127359

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

Источники: ВСОШ, РЭ, 2015, 11.8 (см. olympiads.mccme.ru)

Показать ответ и решение

Первое решение. Обозначим $n= 100.$ Назовём последовательность из $n$ натуральных чисел, любые два соседних члена которой различаются не больше, чем на 2, интересной. Каждой интересной последовательности $a1,a2,...,an$ сопоставим разностную последовательность $bi = ai+1− ai$ $(i= 1,2,...,n − 1$ ).

Все члены разностной последовательности равны 0, $± 1$ или $±2,$ так что количество всевозможных разностных последовательностей равно $n−1 5 .$

Посчитаем сначала количество $S$ всех интересных последовательностей, минимальный член которых не превосходит 5. Рассмотрим произвольную разностную последовательность $b1,b2,...,b99.$ Любые две интересные последовательности, соответствующие ей, отличаются прибавлением одного и того же числа к каждому члену. Значит, среди них ровно по одной последовательности с минимальным членом, равным 1, 2, 3, 4 или 5. Таким образом, $n− 1 n S = 5⋅5 = 5.$

В $S$ учтены все последовательности, выписываемые Петей, и несколько лишних — тех, в которых не встречается ни 4, ни 5. Ясно, что, если в интересной последовательности встречаются как числа, большие 5, так и меньшие 4, то 4 или 5 также встретится. Но минимальный член каждой лишней последовательности не больше 3, значит, и все их члены не превосходят 3. Итак, все лишние последовательности состоят из чисел 1, 2 и 3. С другой стороны, каждая последовательность из чисел 1, 2 и 3 является интересной и, стало быть, лишней.

Итого, лишних последовательностей ровно $3n,$ а значит, искомое количество равно $S − 3n = 5n− 3n.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Назовём хорошей последовательность из $n$ натуральных чисел, в которой хотя бы раз встречается число 4 или 5, а любые два соседних члена различаются не больше, чем на 2. Обозначим через $Sn$ количество хороших последовательностей длины $n.$ Мы докажем индукцией по $n,$ что $Sn =5n− 3n.$ База индукции при $n= 1$ очевидна.

Сделаем переход от $n$ к $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, то хорошую последовательность из неё получить нельзя. Значит, количество полученных неучтённых последовательностей равно $n−1 n−1 n 2⋅3 +3 = 3$ (и ещё столько же получаются из последовательностей с числами 6, 7 и 8).