Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Количество способов, исходов, слагаемых и теория вероятностей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Классическая вероятность

Аксиоматическая вероятность, случайные величины и их моменты (мат.ожидание)

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

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

Задача 1#36173

Сколько существует 5-значных чисел, в которых есть хотя бы одна цифра 5?

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

Подсказка 1

Подумаем, как же удобнее всего учитывать условие на 5? Удобно ли считать конкретно те способы, которые нам нужны, или можно поступить хитрее с помощью тех чисел, которые мы умеем искать?

Подсказка 2

Мы умеем искать количество всех пятизначных чисел, а еще умеем учитывать те числа, в которых нет пятёрки) Для этого просто исключим её из "возможных вариантов" для каждой позиции пятизначного числа! Осталось лишь понять, что же делать с полученными количествами)

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

В данном случае проще сначала посчитать количество пятизначных чисел, в записи которых нет цифры $5$ , а затем вычесть их из $90000$ , то есть количества пятизначных чисел.

Итак, считаем пятизначные числа, в которых нет $5$ . На первом месте может стоять любая из $8$ цифр (кроме $0$ и $5$ ), на втором, третьем, четвёртом и пятом местах — любая из $9$ цифр (кроме $5$ ). Так как цифры выбираются последовательно и выбор очередной цифры не зависит от выбора предыдущих, то эти способы перемножаются. Значит, всего есть $8⋅9⋅9⋅9⋅9= 52488$ пятизначных чисел без $5$ в записи. Тогда пятизначных чисел с цифрой $5$ в записи всего $90000 − 52488 =37512.$

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

Ответ:

$9⋅104− 8⋅94 =37512$

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

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

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

Задача 2#76651

Найдите количество функций $f :{1,2,3,4,5,6} → {1,2,3,4,5,6}$ для которых верно $f(f(f(x)))=x$ для всех $x∈ {1,2,3,4,5,6}$ .

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Возьмем какое-нибудь число $a ∈{1,2,3,4,5,6}.$ Тогда возможны два варианта:

1. Если $f(a)= a,$ то и $f(f(f(a)))= a.$

2. Предположим $f(a)= b и b⁄= a.$ Тогда $f(b)= c, где c⁄= a,c⁄= b.$ Иначе
(а) Если $f(b)= a, то f(f(f(a)))= f(f(b)) =f(a)=b ⁄=a.$
(b) Если $f(b)= b, то f(f(f(a)))= f(f(b))= f(b) =b⁄= a.$
И так как $a =f(f(f(a)))= f(f(b))= f(c),$ то $f(c)=a.$

Таким образом, для любого $a∈ {1,2,3,4,5,6}$ либо $f(a)=a,$ либо есть три различных числа таких, что $f(a)= b,f(b) =c и f(c)= a.$

При этом любая функция с таким свойством подходит. Тогда найдем число функций с необходимым свойством.

1. Нет ни одной тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Значит, для всех чисел $a∈{1,2,3,4,5,6}$ верно $f(a)= a.$ Такая функция одна.

2. Есть одна тройка элементов, что $f(a)= b,f(b)= c, и f(c)=a.$ Выбрать тройку можно $C36$ способами. При этом есть два способа задать функцию в тройке. Итого $2C36$ функций.

3. Есть две тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Выбрать первую тройку можно $C36$ способами, остальные три элемента образуют вторую тройку. Но варианты, в которых выбрали в первую тройку $a,b,c$ и выбрали все кроме $a,b,c$ одинаковые. То есть $C36 :2$ способов разбить элементы на две тройки. При этом в каждой тройке есть два способа задать функцию. Итого $2⋅2⋅C36 :2 =2C36$ функций.

Всего число функций равно

1 +2C36 + 2C36 = 81

Ответ: 81

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

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

В азбуке Морзе любой символ (буква или цифра) зашифрован последовательностью точек и тире.

(a) Сколько различных символов можно зашифровать, если использовать последовательность, содержащую ровно пять символов?

(b) А если использовать последовательность, содержащую не более пяти символов?

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

$(a)$ Каждый из 5 элементов последовательности точек и тире можно выбрать двумя способами, поэтому количество символов, которые можно закодировать, равно $5 2 ⋅2 ⋅2 ⋅2 ⋅2 =2 = 32.$

$(b)$ Символ может кодироваться последовательностью из одного, двух, трех, четырех или пяти элементов. В каждом случае ответ считается аналогично предыдущему пункту и равны соответственно $2 3 4 5 2,2 ,2 ,2,2 .$ Осталось сложить все эти числа: $2 3 4 5 2+ 2 + 2 +2 + 2 = 2+4 +8+ 16+ 32 =62.$

Ответ:

$(a) 32;$

$(b) 62.$

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

Задача 5#82692

Будем называть номером последовательность из 6 цифр.

(a) Сколько всего существует различных номеров? А номеров, все цифры которых чётны?

(b) Сколько номеров, в которых любые две соседние цифры различны?

(d) Сколько номеров, все цифры которых имеют одинаковую четность?

(e) Сколько номеров, у которых есть хоть одна нечетная цифра?

(f) Сколько номеров, содержащих цифру 7 и не содержащих цифры 0?

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

(a) На каждую позицию номера можно выбрать одну из $10$ цифр, поэтому всего номеров $106.$ Так как четных цифр всего $5$ , то, выбирая на каждую позицию одну из пяти четных цифр, получаем, что номеров с четными цифрами всего $6 5 .$

(b) Пусть первая цифра выбирается произвольным образом - для нее есть $10$ вариантов. Тогда следующая цифра может быть выбрана девятью способами, так как нельзя использовать ту цифру, которая была выбрана первой. Аналогичными рассуждениями приходим к тому, что на каждой из позиций цифра может быть выбрана произвольным образом из некоторых девяти цифр. Тогда число номеров, в которых соседние цифры различны, равно $5 10×9 .$

(c) Первую цифру можно выбрать $10−$ ю способами. Вторую цифру - $9−$ ю, так как нельзя использовать цифру, стоящую на первом месте. Третья цифра может быть выбрана $8−$ ю способами, так как теперь не могут быть использованы цифры с первого и второго мест. Рассуждая аналогично, получаем, что для оставшихся мест имеется $7,$ $6$ и $5$ способов соответственно. Получаем, что искомое число равно $10× 9×8 ×7× 6× 5.$

(d) Выберем первую цифру произвольным образом (есть $10$ способов.) После того, как первая цифра была выбрана, была выбрана и четность оставшихся пяти цифр, и для каждой из них остается ровно $5$ вариантов выбора. Тогда количество номеров с четными или нечетными цифрами равно $10× 55.$

(e) Если из общего числа номеров вычесть число номеров, в которых все цифры четны, получим число номеров, в которых есть хотя бы одна нечетная цифра. Тогда число номеров с нечетной цифрой равно $106 − 56.$

f Вычтем из числа номеров, не содержащих $0$ , число номеров, не содержащих цифр $7$ и $0.$ Ясно, что это и будет искомым числом, так как тогда останутся номера, не содержащие $0,$ но в которых есть $7.$ Номеров без нулей всего $96,$ так как каждую цифру можно выбрать девятью способами. Число цифр, в которых нет еще и цифры $7$ равно $86,$ так как каждая из цифр может быть выбрана восьмью способами. Таким образом, искомое число номеров равно $96 − 86.$

Ответ:

$(a)$ $106,$ $56;$

$(b)$ $5 10⋅9;$

$(c)$ $151200;$

$(d)$ $5 10⋅5 ;$

$(e)$ $6 6 10 − 5;$

$(f)$ $6 6 9 − 8 .$

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

Задача 6#82693

Сколько десятизначных чисел, в которых все цифры различны, и при этом цифры 4 и 5 стоят рядом?

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

Решение скрыто

Ответ:

Курсы

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

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

Задача 7#82694

Сколько существует пятизначных чисел, сумма цифр которых делится на 5?

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

Будем последовательно выбирать цифры от первого места к последнему.

На первом месте могла оказаться любая цифра, кроме $0.$ На втором, третьем и четвертом местах могла оказаться любая цифра. Осталось выбрать цифру на последнее место. Для этого рассмотрим, какие могли быть остатки у суммы первых четырех выбранных цифр. Обозначим этот остаток через $s,$ а последнюю цифру через $r.$

Если $s =0,$ то $r =0$ или $r= 5$
Если $s =1,$ то $r =4$ или $r= 9$
Если $s =2,$ то $r =3$ или $r= 8$
Если $s =3,$ то $r =2$ или $r= 7$
Если $s =4,$ то $r =1$ или $r= 6$

Заметим, что для каждого $s$ можно выбрать последнюю цифру двумя способами. Это значит, что последнюю цифру нашего числа можно выбрать двумя способами. Тогда количество чисел, сумма цифр которых делится на 5, равно

9× 10× 10 ×10× 2= 18000

Ответ: 18000

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

Задача 8#82700

Человек-Паук и Человек-Муравей поспорили о том, кто из них раньше получит новый костюм. За костюмом выстроились $10$ мстителей, включая этих двоих. Известно, что в споре победил Человек-Паук. Сколько всего существует очередей, в которых побеждает Человек-Паук?

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

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

Всего возможных очередей имеется

10⋅9⋅...⋅2⋅1= 10!

Тогда победных очередей для человека-паука ровно $10!. 2$

Ответ:

$10! 2$

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

Задача 9#82701

Перед Наташей лежит доска $10× 10$ . Она хочет обвести по контуру на этой доске клетчатый прямоугольник. Сколькими способами Наташа может это сделать? Прямоугольники одинакового размера, но отмеченные в разных местах, считаются различными.

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

Будем выбирать 4 точки - вершины прямоугольника. Первую вершину можно выбрать произвольным образом в одном из узлов квадрата $10× 10,$ которых всего имеется $11⋅11= 121,$ так как в строке и в столбце по $11$ узлов. Далее выбираем точку в той же горизонтали одним из $10$ способов. После этого выбираем точку в той же вертикали, тоже одним из $10$ способов. Последняя вершина задается однозначно тремя предыдущими. Тогда получаем $121⋅10⋅11⋅1$ вариантов. Заметим, что каждый прямоугольник посчитан 4 раза, так как есть 4 способа выбрать первую вершину прямоугольника. Таким образом, всего прямоугольников

121⋅10⋅10⋅1:4= 3025

Ответ: 3025

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

Задача 10#82778

Болельщики должны выбрать 6 лучших хоккеистов чемпионата: одного вратаря, двух защитников и трех нападающих. Среди претендентов: 2 вратаря, 5 защитников, 6 нападающих и 3 “универсала”. “Универсал” — игрок, хороший в разных ролях, который поэтому может быть выбран как в качестве защитника, так и в качестве нападающего (но не вратаря). Сколько существует способов выбрать эту шестёрку? Требуется получить числовое значение.

Источники: Ломоносов - 2024, 11.1 (см. olymp.msu.ru)

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

Подсказка 1

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

Подсказка 2

Давайте сначала выберем вратаря, ведь место вратаря мажет занять только вратарь. Всего у нас два варианта на эту позицию. Обратите внимание, что защитников нужно выбрать только двое, и наша задача легко разбивается на три случая. Первый случай — это 0 универсалов среди защитников, второй — 1 универсал, третий — 2 универсала.

Подсказка 3

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

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

Начнём считать с вратарей. Место вратаря может занять только вратарь, поэтому у нас всегда всего 2 способа выбрать его.

Дальше рассмотрим три случая по количеству универсалов на месте защитников:

1. Среди выбранных защитников нет универсалов. Значит, количество так выбрать двух защитников в команду равно

2 5⋅4 C5 =-2- =10

На место нападающих в этом случае мы можем поставить либо нападающих, либо универсалов, следовательно, способов

C39 = 9⋅83⋅!7 =84

Следовательно, вариантов команд в этом случае

2⋅10 ⋅84= 1680

2. Среди выбранных защитников один универсал. Значит, количество так выбрать двух защитников в команду равно

5⋅3= 15

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшихся универсалов, следовательно, способов

C38 = 8⋅7⋅6 =56 3!

Следовательно, вариантов команд в этом случае

2⋅15 ⋅56= 1680

3. Среди выбранных защитников оба являются универсалами. Значит, количество так выбрать двух защитников в команду равно

C23 = 3

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшегося универсала, следовательно, способов

7⋅6⋅5 C37 =--3!- =35

Следовательно, вариантов команд в этом случае

2 ⋅3 ⋅35= 210

В итоге способов выбрать команду равно

1680+ 1680+ 210 =3570

Ответ: 3570

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

Задача 11#83300

Найти коэффициент $a 49$ многочлена $P(x)= (1+x15+ x17)6$ , если бы он был приведен в форму суммы одночленов вида $k akx ,k = 0,2,3,...,102$ .

Источники: Росатом - 2024, московский вариант, 11.5, по мотивам 10.2 ММО - 2005 (см. olymp.mephi.ru)

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

Подсказка 1

Обратим внимание на степени переменных. Понятно, что при раскрытии скобок для каждого одночлена степень будет вида 17n+15m. Тогда найдём натуральные решения для 17n+15m=49

Подсказка 2

Правильно, единственное решение - (2;1). То есть при перемножении скобок мы 2 раза взяли х¹⁷ и 1 раз х¹⁵. Обратим внимание также, что в заданной скобке перед каждым одночленом коэффициент 1. Как тогда мы можем выразить коэффициент перед х⁴⁹?

Подсказка 3

Конечно, коэффициент перед х⁴⁹ равен количеству способов выбрать комбинацию из двух х¹⁷ и одного х¹⁵ в 6 скобках. Остаётся только это досчитать

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

Понимаем, что при раскрытии скобок степень каждого одночлена будет иметь вид $17n +15m,$ где $n$ — количество взятых $x17,m$ — количество взятых $15 x .$ Поэтому решим сначала уравнение в натуральных числах

17n +15m = 49

Нетрудно заметить решение $n= 2,m =1,$ а также что это решение единственное, т.к. иначе, чтобы сохранить нужные остатки, $x$ будет изменяться на кратное 15 число, а $y$ на кратное 17, поэтому одно из них станет отрицательным.

Осталось лишь посчитать количество способов выбрать комбинацию из двух $x17$ и одного $x15$ в 6 скобках:

2 1 6⋅5 C6 ⋅C 4 = 2 ⋅4= 60

Ответ: 60

Интенсивы

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

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

Задача 12#86092

Три человека независимо задумали по одному целому числу от $1$ до $9$ . Какова вероятность, что произведение этих трёх чисел делится на $10$ ?

Источники: Бельчонок - 2024, 11.1 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Давайте подумаем, что такое делимость на 10. Собственно, думать нечего - это делимость на 2, и на 5. Тогда, давайте рассмотрим вероятность противоположного события - что произведение трех чисел не делится на 10. Чему равна вероятность этого события, если мы хотим это выразить через вероятности событий про неделимость 2 и 5(это простые числа, они легче считаются)?

Подсказка 2

Верно, вероятность неделимости на 10 равна сумме вероятностей делимости на 2 и 5 - не делимость и на, и на 5. Осталось посчитать эти вероятности, получить вероятность того, что не делится на 10, вычесть ее из 1 и получить ответ.

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

Обозначим событие $A = {$ Произведение $3$ чисел не делится на $10}$ , $B = {$ Среди $3$ чисел нет $5},C = {$ Среди $3$ чисел нет чётного $}.$ Тогда

P(A)= P(B+ C)= P(B)+ P(C)− P (BC )=

(8)3 ( 5)3 (4)3 = 9 + 9 − 9

Вероятность искомого события равна

( )3 ( )3 ( )3 1− 8 − 5 + 4 = -52 9 9 9 243

Ответ:

$-52 243$

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

Задача 13#86094

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

Источники: Бельчонок - 2024, 11.3 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

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

Подсказка 2

Можно решить задачу, в которой каждая белка либо осталась на своем месте, либо перешла на соседнее. Задача стала проще, можно перебрать все случаи

Подсказка 3

Все бельчата могут оставаться на месте, перемещаться по часовой стрелке или против часовой стрелки. Какие случаи могут быть, если пара соседних бельчат поменяются местами?

Подсказка 4

Каждая пара может поменяться, а может остаться на месте. Но один случай мы уже учли. Тогда вариантов 7 + 7 (пары могут образоваться двумя способами). Какой еще случай мы не учли?

Подсказка 5

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

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

Любой рассадке вечером можно сопоставить рассадку, в которой белка, сидевшая на дереве с номером $x$ (нумерация по часовой стрелке), сидит на дереве $(x+ 3)$ по модулю 6 (то есть просто белку переместили на противоположное место). Нетрудно видеть, что это противоположное место является либо тем местом, на котором белка сидела утром, либо соседним с ним. Значит, можно решить задачу, в которой каждая белка либо осталась на своём месте, либо перешла на соседнее.

Пусть изначально белки сидели в порядке $ABCDEF$ . Рассмотрим случаи:

$1)$ Все остаются на своих местах. Тогда есть только один случай ( $ABCDEF$ ).

Если $A$ перемещается вправо на место $B$ , у $B$ есть два варианта действий. $B$ может переместиться влево(на место $A$ ) или переместиться вправо на место $C$ .

$2)$ Рассмотрим движение по кругу. Если $B$ перемещается на место $C$ , то единственный способ для $C$ — переход к $D$ , переход $D$ к $E$ , переход $E$ к $F$ и переход $F$ к $A$ , в результате чего достигается $F ABCDE$ . Каждый бельчонок может также двигаться влево( $BCDEF A$ ). Таким образом, тут два случая.

$3)$ Некоторые бельчата из соседних пар $AB$ , $CD$ , $EF$ меняются местами, оставаясь в той же паре. Если $A$ перемещается на место $B$ , $B$ перемещается на место $A$ . $C$ может остаться на месте, или переместиться на $D$ , $E$ может остаться на месте, или переместиться на $F$ . Это даёт $2⋅2⋅2= 8$ случаев, но бельчата не могут все оставаться на месте, поскольку мы уже посчитали такую возможность в случае $1$ , и, следовательно, здесь $7$ случаев. Кроме этого, могут быть пары $BC,DE,F A$ что даёт еще $7$ случаев.

$4)$ Меняются местами не в соседних парах, а в парах, разделённых одним бельчонком. Если бы $A$ и $B$ поменялись местами, $D$ и $E$ могли бы поменяться местами, и это не было бы учтено предыдущими группировками. При этом два бельчонка, разделяющие пары, сидят на прежних местах. Это может происходить в трёх случаях ( $A$ и $D$ не движутся, $B$ и $E$ не движутся, $C$ и $F$ не движутся).

Всего случаев $1 +2+ 7+ 7+ 3= 20$ .

Ответ: 20

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

Задача 14#86097

Если сегодня плохая погода, то завтра с вероятностью 1 будет хорошая погода. Если сегодня хорошая погода, то завтра хорошая погода будет с вероятностью 0,4. Какова вероятность, что 7 марта будет хорошая погода, если 3 марта плохая и хорошая погоды равновероятны? (Погода одинаковая весь день и может быть только плохой или хорошей).

Источники: Бельчонок - 2024, 11.1 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Пусть P_n - вероятность хорошей погоды в n-ый день. Как выразить его с помощью P_{n-1}?

Подсказка 2

Заметим, что формула должна быть такой: Если в n-1-й день погода плохая, то в n-й она точно хорошая, а если хорошая, то в n- м дне будет хорошей с вероятностью 0,4.

Подсказка 3

P_n = 0.4 * P_{n-1} + (1 - P_{n-1})

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

Обозначим $P n$ вероятность хорошей погоды в день $n$ считая $3$ марта за первый день. Тогда

Pn = 0,4Pn−1+ (1− Pn−1)= 1− 0,6Pn

(Если в $n− 1$ -й день погода плохая, то в $n$ -й она точно хорошая, а если хорошая, то в $n$ -м дне будет хорошей с вероятностью $0,4$ ). По условию $P1 = 1 2$ . Находим последовательно

P2 =0,7

P = 0,58 3

P4 = 0,652,P5 =0,6088

Ответ:

0,6088

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

Задача 15#86344

Буквы в симметричном слове АРБУЗУЗУБРА случайно переставили так, что полученное слово отличается от исходного. С какой вероятностью это слово снова будет симметричным? Ответ запишите в виде несократимой дроби.

Источники: ШВБ - 2024, 11.1 (см. olymp.bmstu.ru)

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

Подсказка 1

Что такое вероятность в этой задаче? Количество способов расставить буквы симметрично, отнесенное к количеству способов расставить их как угодно. Нам надо комбинаторно вычислить оба эти количества. Не забываем, что некоторые буквы одинаковые!

Подсказка 2

Чтобы посчитать количество симметричных слов, надо понять, как они вообще образуются. Если, допустим, мы решили ставить А на первое место, то на последнем тоже автоматически оказывается А. После таких наблюдений понятно, сколько мест у нас с выбором, а сколько “заполняется автоматически”.

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

Всего способов переставить 11 букв (из них по 3 У и по 2 А, Р, Б, З)

----11!---- 11! 2!⋅2!⋅2!⋅2!⋅3! = 96

Чтобы слово было симметричным, на $6$ позиции должна стоять буква У (иначе не будет симметрии, так как оставшиеся буквы идут парами). На позициях с первой по пятую можно поставить $5!$ способами любую последовательность букв. Тогда, чтобы была симметрия, буквы на оставшихся позициях определяются однозначно.

Не учитывая исходное слово, вероятность равна частному количества подходящих исходов (слово симметричное и отличается от исходного) и всех исходов (слово отличается от исходного), то есть

151!−!-1-= -119- -96-− 1 415799

Ответ:

$--119- 415799$

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

Задача 16#87528

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

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

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

Подсказка 1

А что если не было бы условия на два дня голодовки? Сколько способов было бы?

Подсказка 2

Нам нужно выбрать всего 4 дня из 10, а остальные будут обжорными. А как посчитать количество способов, которые не подходят под условие?

Подсказка 3

Нам нужно вычесть способы, в которых есть хотя бы 3 дня подряд голодовки. Много ли таких случаев?

Подсказка 4

Разберите случаи: когда у нас есть 3 дня подряд голодовки и 1, не стоящий рядом с ними. И второй случай: все 4 дня голодовки стоят рядом

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

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

4 10⋅9⋅8⋅7 C10 =---4!---= 210

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

1) У нас 3 голодных дня подряд и 1 голодный, не стоящий с ними рядом. Будем воспринимать эти 3 дня как 1, назовём его большой голодный день, т.е. теперь у нас будет 8 дней и мы распределяем большой голодный день и голодный день так, чтобы они не стояли рядом. Если большой голодный стоит первым или последним, то у обычного есть 6 вариантов, в иных случаях у него их 5. В итоге

2⋅6+ 6⋅5= 42

2) У нас 4 голодных дня подряд. Количество таких способов равно количеству способов выбрать место для первого голодного дня, оно равно 7.

В итоге количество способов распределения, подходящих под условия равно

210 − 42− 7= 161

Ответ: 161

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

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

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

Задача 17#90003

Сколькими способами из множества ${1,2,3,...,2024}$ можно выбрать $n$ чисел так, чтобы сумма любых $m$ (произвольное натуральное число, меньшее $n$ ) из выбранных чисел не делилась на 3? Рассмотрите все возможные $n ≥ 2.$

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

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

Подсказка 1

Нужно рассмотреть все натуральные n>=2... как будто это очень много чисел.. Значит, нужно как-нибудь сузить круг поиска. Подумайте, может ли n быть больше трех?

Подсказка 2

Правда ли, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём?

Подсказка 3

Это действительно так! Получается n<=3, то есть нам нужно рассмотреть всего два варианта! Для подсчёта используйте число сочетаний и рассматривайте остатки при делении на 3.

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

Заметим, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём. (Ведь не может быть числа, кратного трём, и не могут быть одновременно числа с остатками $1$ и $2$ , а чисел одного остатка не более двух).

А значит, $n ≤3,$ при этом из условия нас интересуют $n≥ 2.$ В рассматриваемом множестве чисел по $675$ чисел, дающих остатки $1$ и $2$ при делении на $3.$

Тогда для $n= 3$ подходят любые три числа с одинаковыми остатками, их $3 2⋅C675.$ Для $n = 2$ любая пара чисел с ненулевыми остатками, то есть $2 2⋅C675$ пар чисел с одинаковыми остатками и $2 675$ с разными.

Итого $2 3 2 3 2 2 ⋅C 675+ 2⋅C675+ 675 =2 ⋅C 676+ 675 = 102971025$ чисел.

Ответ:

$2⋅C3 + 6752 = 102971025 676$

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

Задача 18#90004

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

- если полицейский войдет в подъезд, в котором укрылся преступник, то гарантированно поймает его;

- если полицейский войдет в подъезд, где преступника нет, то с вероятностью $1 6$ тот убежит через выход из двора (и поймать его уже не удастся), с вероятностью $1 2$ преступник никуда не переместится, и с вероятностью $1 3$ спрячется в другом подъезде, где полицейского сейчас нет;

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

С какой вероятностью полицейский поймает преступника? Перемещения между подъездами можно считать мгновенными.

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

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

Подсказка 1

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

Подсказка 2

У нас получается бесконечный граф, но достаточно записать вероятности лишь нескольких первых ходов. Далее вероятности будут одинаковы: если полицейский не угадывает подъезд и преступник не сбегает, то вероятность не изменится. Мы можем составить уравнение.

Подсказка 3

Осталось только просуммировать вероятности, когда полицейский ловит преступника, и получить ответ.

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

С вероятностью $1 3$ полицейский поймает преступника в первом же подъезде, в который зайдёт, и с вероятностью $2 3$ преступника там не окажется, значит, с вероятностью $2 1 1 3 ⋅6 = 9$ преступник сбежит из двора (сразу после первого захода полицейского в подъезд), и с вероятностью $2 5 5 3 ⋅6 = 9$ преступник так или иначе окажется в одном из подъездов, где сейчас нет полицейского.

Построим дерево, отображающее все возможные (на рёбрах написаны соответствующие условные вероятности):

Оказавшись в точке $B$ полицейский будет иметь выбор из двух подъездов, и с равной вероятностью поймает преступника в любом из них, этим обусловлены вероятности $1 2$ поймать преступника и дать ему скрыться в другом подъезде. После чего преступник снова либо сбежит со двора с вероятностью $1 6,$ либо останется в подъезде, где нет полицейского.

Заметим, что вероятность поймать преступника в точке $B$ равна вероятности поймать преступника в точке $C,$ обозначим эту вероятность за $P.$ Тогда, учитывая все возможные события в точке $B,$ получим $1 5- P = 2 + 12 ⋅P,$ отсюда $6 P =7.$ Учитывая события из точки $A,$ вероятность поймать преступника $1 5 17 3 + 9 ⋅P =21.$

Ответ:

$17 21$

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

Задача 19#91045

Сколько существует 6-значных чисел, в которых любые две соседние цифры различны?

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

Первой цифрой числа может быть любая из $1,2,...,9,$ потому что число не может начинаться с $0.$ Вторую цифру можно выбрать $9$ способами, так как всего цифр $10$ , при этом вторая цифра должна отличаться от соседней первой. Аналогично третью цифру можно выбрать $9$ способами, потом четвертую $9$ способами и так далее. Получаем ответ:

6 9⋅9⋅9⋅9⋅9⋅9= 9

Ответ:

$96$

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

Задача 20#91046

Сколько существует 6-значных чисел, в которых есть цифра “5”?

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

Посчитаем количество всех шестизначных чисел: первую цифру можно выбрать любым из $9$ способов (любая кроме $0$ ), а последующие любым из $10.$ Всего шестизначных чисел:

5 9⋅10

Посчитаем количество шестизначных чисел, не содержащих “5”: первую цифру можно выбрать любым из $8$ способов (любая кроме $0,5$ ), а последующие любым из $9.$ Всего шестизначных чисел, не содержащих “5”: