Тема Количество способов, исходов, слагаемых и теория вероятностей

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

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

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

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

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

Подтемы раздела количество способов, исходов, слагаемых и теория вероятностей

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

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

Задача 1#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)!!$

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

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

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

Задача 2#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$

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

Задача 3#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

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

Задача 4#35433

Найдите количество слов длины 10, состоящих только из букв “а” и “б” и не содержащих в записи двух букв “б” подряд.

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

Обозначим через $a n$ количество слов длины $n$ , состоящих только из букв “а” и “б” и не содержащих в записи двух букв “б” подряд. Таким образом, находим $a1 = 2$ , $a2 =3$ . Покажем, что $an$ можно выразить через $an−1$ и $an−2$ . Количество слов длины $n$ , не содержащих в записи двух букв “б” подряд и начинающихся с буквы “а”, равно $an−1$ , так как после первой буквы может следовать любое слово длины $n − 1$ , не содержащее двух “б” подряд. Пусть слово длины $n$ начинается с буквы “б”. Если в этом слове нет двух “б” подряд, то вторая буква — “а”, а далее может следовать любое слово длины $n− 2$ , не содержащее двух “б” подряд. Таким образом, количество слов длины $n$ , не содержащих в записи двух букв “б” подряд и начинающихся с буквы “б”, равно $an−2$ . Тем самым, мы показали, что $an =an−1+ an−2$ . Теперь последовательно вычисляем $a3 = a2+a1 = 3+ 2= 5$ , $a4 = a3+a2 = 5+ 3= 8$ и так далее, $a10 = a9+a8 = 144$ .

Ответ: 144

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

Задача 5#35434

Сколько существует последовательностей из 1 и 2, таких что сумма чисел в каждой такой последовательности равна $n$ ? Например, если $n =4$ , то таких последовательностей пять: 1111, 112, 121, 211, 22.

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

Обозначим через $a i$ количество таких последовательностей с суммой $i$ . Будем доказывать, что $a= f i i+1$ . Для $i= 1$ это очевидно верно. пусть у нас есть некоторая последовательность для $i+ 1$ , тогда если в ней на последнем месте стоит число 1, то все оставшиеся числа образуют последовательность с суммой $i$ , то есть таких последовательностей $ai$ . Если же на последнем месте стоит число $2$ , то по аналогичным рассуждениям количество таких последовательностей равно $ai−1$ . То есть $ai+1 =ai+ ai− 1$ , и при этом $a1= 1$ , $a2 = 2$ , следовательно наша последовательность и есть последовательность чисел Фибоначчи, начиная со второго члена.

Ответ: f_{n+1}

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

Задача 6#35435

Можно ли сделать набор из 10 гирек, каждая весит целое число граммов, с помощью которых можно взвесить любой целый вес от 1 до 55 граммов включительно даже в том случае, если одна из гирек потеряется (гирьки кладутся на одну чашку весов, измеряемый вес — на другую)?

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

Возьмем гирьки с весами $f,f,...,f 1 2 10$ . Докажем для любого натурального $n$ , что, даже потеряв одну гирю из набора гирь $f ,f ,...,f 1 2 n$ , можно составить любой вес от 1 до $fn+1− 1$ . Для $n =1$ утверждение очевидно.

Докажем, что если утверждение верно для $n − 1$ , то верно и для $n$ . Если вес $S < fn$ , то его можно взвесить уже набором $f1,f2,...,fn−1$ с потерей одной гири. Пусть $S ≥ fn$ . Если не потеряна $fn$ , то вес $S− fn$ можно взвесить с помощью гирь $f1,f2,...,fn−1$ (с потерянной гирей) и добавить гирю $fn$ . Если $fn$ потеряна, то $fn−1$ не потеряна. Вычитая её из $S$ , получим вес, меньший $fn+1− fn− 1 =fn$ . Его можно взвесить с помощью набора $f1,f2,...,fn− 1$ с потерянной гирей $fn−1$ . Добавив $fn−1$ , получим $S$ .

Ответ: Можно

Курсы

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

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

Задача 7#35436

Загадано число от 1 до 144. Разрешается выделить одно подмножество множества чисел от 1 до 144 и спросить, принадлежит ли ему загаданное число. За ответ да надо заплатить 2 рубля, за ответ нет — 1 рубль. Как, потратив не более 11 рублей, определить загаданное число?

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

Заметим, что $144 =f 11$ . Будем доказывать, что нам хватит $n$ рублей, чтобы найти число среди $f n$ различных натуральных чисел. Выделим произвольное множество из $fn− 2$ чисел и спросим про него. Если нам ответили утвердительно, то мы заплатили 2 рубля и спустились на 2 числа Фибоначчи. Если же нам ответили отрицательно, то мы переходим в оставшееся множество и спускаемся к предыдущему числу Фибоначчи, заплатив 1 рубль. Такими действиями мы найдем нужное число, потратив как раз не более $n$ рублей.

Ответ:

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

Задача 8#35440

55 боксеров участвовали в турнире по системе “проигравший выбывает”. Бои шли последовательно. Известно, что у участников каждого боя количества предыдущих побед отличались не более чем на 1. Какое наибольшее количество боев мог провести победитель турнира?

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

Докажем для любого натурального $n$ , что если победитель провёл не меньше $n$ боёв, то число участников не меньше $fn+2$ , а также, что существует турнир с $fn+2$ участниками, победитель которого провёл $n$ боёв. Для $n= 1$ оба условия очевидны.

Пусть победитель A выиграл последний бой у боксёра B. Оставшиеся поединки фактически распадаются на два турнира: один из них выиграл A, а второй – B. В первом турнире победитель A провёл не меньше $n− 1$ боя, значит, число участников не меньше $fn+1$ . Во втором турнире победитель B провёл не меньше $n− 2$ боёв, значит, число участников не меньше $fn$ . Но тогда в исходном турнире число участников не меньше $fn+1+ fn = fn+2$ .

Пример же будем строить, опираясь на примеры для меньших $n$ . Достаточно свести в заключительном поединке победителя турнира с участниками, выигравшего $n− 1$ бой, и победителя турнира с $fn$ участниками, выигравшего $n − 2$ боя.

Поскольку $55= f10$ , отсюда следует ответ.

Ответ: 8

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

Задача 9#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

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

Задача 10#78846

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

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

Подсказка 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$

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

Задача 11#95761

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

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

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

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

Ответ:

$144$

Предыдущий раздел

Следующий раздел