Комбинаторика на Бельчонке: способы, вероятности, графы, турниры —Каталог задач по Олимпиадной математике

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

Тема Бельчонок

Комбинаторика на Бельчонке: способы, вероятности, графы, турниры

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

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

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

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

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

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

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

Задача 1#86097

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

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

Подсказка 1

Пусть P_n - вероятность хорошей погоды в n-ый день. Как выразить его с помощью 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

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

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

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

Задача 2#86094

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

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

Любой рассадке вечером можно сопоставить рассадку, в которой белка, сидевшая на дереве с номером $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

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

Задача 3#86092

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

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

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

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

Задача 4#69407

Несколько команд провели турнир по футболу, каждая команда сыграла с каждой по разу. За победу начислялось 3 очка, за ничью — 1 очко, за проигрыш очков не давалось. Команда “Бельчата” заняла первое место, набрав больше всего очков, а команда “Метеор” — последнее место, набрав меньше всего очков. Если бы за победу давали не 3 очка, а 2, то наоборот, команда “Метеор” стала бы первой, а команда “Бельчата” — последней. Найдите наименьшее количество команд, которое могло участвовать в таком турнире.

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

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

Подсказка 1

Подумайте, какая минимальная разница в очках могла быть между командами «Метеор» и «Бельчата» до пересчёта и после.

Подсказка 2

Каждая команда сыграла с каждой, а это значит, что победитель турнира имел хотя бы на два очка больше, чем команда, занявшая последнее место. Данное утверждение верно и для ситуации до пересчета, и после. Подумайте, каким количеством побед должна была обладать команда «Метеор», чтобы после пересчета у неё были шансы оказаться в лидерах, а также над количеством необходимых побед и поражений команды «Бельчата».

Подсказка 3

Команде «Метеор» необходимо иметь хотя бы одну победу, чтобы набрать больше половины очков и иметь возможность стать победителем. Значит, «Метеор», имея одну победу, потеряет на пересчете 1 балл. Сколько баллов, в таком случае, должна потерять команда «Бельчата» и сколько ей необходимо иметь для этого побед и поражений, чтобы оказаться на последнем месте? На основе полученной оценки не забудьте построить пример.

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

Оценка: До пересчёта у команды «Бельчата» было хотя бы на 2 очка больше, чем у команды «Метеор», а после пересчёта - хотя бы на 2 очка меньше. Кроме того, чтобы после пересчёта оказаться первой, команда «Метеор» должна иметь хотя бы одну победу. Действительно, в каждом матче разыгрывается 2 очка, поэтому если бы у команды «Метеор» не было побед, то она набрала бы не более половины возможного числа очков и не могла бы стать первой. Аналогично, для того чтобы команда «Бельчата» стала последней, у неё должно быть поражений больше, чем побед. Таким образом, после пересчёта команда «Метеор» потеряет как минимум 1 очко. Следовательно, команда «Бельчата» должна потерять не менее 5 очков, т. е. у неё должно быть не меньше пяти побед и не меньше шести поражений. Поэтому она сыграла как минимум 11 матчей, значит, в турнире участвовало не менее 12 команд.

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


Команда	$Б$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$M$	Сумма 1	Сумма 2

$Б$		B	B	B	B	B	0	0	0	0	0	0	15	10

$2$	0		1	1	1	1	$B$	$B$	$B$	0	0	1	14	11

$3$	0	1		1	1	1	0	$B$	$B$	$B$	0	1	14	11

$4$	0	1	1		1	1	0	0	$B$	$B$	$B$	1	14	11

$5$	0	1	1	1		1	$B$	0	0	$B$	$B$	1	14	11

$6$	0	1	1	1	1		$B$	$B$	0	0	$B$	1	14	11

$7$	$B$	0	$B$	$B$	0	0		1	1	1	1	1	14	11

$8$	$B$	0	0	$B$	$B$	0	1		1	1	1	1	14	11

$9$	$B$	0	0	0	$B$	$B$	1	1		1	1	1	14	11

$10$	$B$	$B$	0	0	0	$B$	1	1	1		1	1	14	11

$11$	$B$	$B$	$B$	0	0	0	1	1	1	1		1	14	11

$M$	$B$	1	1	1	1	1	1	1	1	1	1		13	12

Ответ: 12

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

Задача 5#69404

Андрей, Боря, Вася, Гриша, Денис и Женя после олимпиады собрались в кинотеатр. Они купили билеты на 6 мест подряд в одном ряду. Андрей и Боря хотят сидеть рядом, а Вася и Гриша не хотят. Сколькими способами они могут сесть на свои места с учётом их пожеланий?

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

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

Подсказка 1

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

Подсказка 2

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

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

Число способов рассадки, когда Андрей и Боря сидят рядом, равно $2 ⋅5!= 240$ (достаточно объединить их в одного человека двумя способами). Способов рассадки, при которых и Андрей-Боря, и Вася-Гриша окажутся рядом, равно $2 ⋅2 ⋅4!= 96.$ Поэтому они могут сесть $240− 96 =144$ способами.

Ответ: 144

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

Задача 6#69402

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

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

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

Подсказка 1

Пупупу… давайте попробуем получить оценку сверху на количество ничьих! Для этого, попробуйте построить примеры для N=2, 3, 4 и 5. Причём примеры такие, в которых количество ничьих максимально!

Подсказка 2

Да, мы получили оценку на N²/4. Остаётся придумать как доказать, что эта формула работает для любого N!

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Для построения примера, попробуйте посмотреть на маленькие N и воспользоваться идеей разбиения элементов от 1 до N на два непересекающихся множества. Также, возможно, Вам придётся строить пример в зависимости от четности N.

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

Решим задача для произвольного $N.$ Докажем утверждение, известное в олимпиадных кругах как теорема Турана.

Оценка: Докажем по индукции, что число ничьих не превосходит $N2 4 .$

База индукции: При $N = 2$ это очевидно. При $N = 3$ все три игры не могли закончиться вничью, иначе у всех команд было бы одинаковое число очков.

Шаг индукции: Рассмотрим две команды $A$ и $B,$ сыгравшие вничью. С каждой из остальных команд хотя бы одна из них сыграла не вничью, иначе образуется запрещенная тройка команд. Значит, общее число ничьих в играх с участием этих двух команд не больше $N − 1.$ По предположению индукции в играх между остальными командами было не более $(N−2)2 4$ ничьих. Следовательно, общее число ничьих не превосходит $(N−2)2 2 --4-- +N − 1= N4-.$

Пример: Пронумеруем команды числами от $1$ до $N.$ Пусть каждые две команды с номерами разной чётности сыграли вничью, а в играх между командами с номерами одной чётности победила команда в меньшим номером. Если $N = 2k− 1,$ то $k$ команд имеют нечётный номер и $k− 1$ команда - чётный, поэтому количество ничьих равно $k(k− 1).$ При $N =2k$ получаем по $k$ команд с номерами каждой чётности и $k2$ ничьих. В обоих случаях полученное число равно $[ 2] N4 .$ При этом каждые три команды в играх между собой набрали либо 0, 2 или 4 очка, если имеют номера одной чётности, либо $1,2,3$ очка, если две из них имеют номера одной чётности, а третья - другой.

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

Подставим $N = 16$ и получим ответ.

Ответ: 64

Курсы

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

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

Задача 7#69399

У бельчонка есть 5 орехов, 8 грибов и 11 ягод. Сколькими способами он может выложить все эти предметы в ряд так, чтобы никакие две ягоды не лежали рядом?

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

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

Подсказка 1

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

Подсказка 2

Ягоды не должны лежать рядом друг с другом. Значит, теперь, когда мы разложили грибы и орехи, у нас есть 14 позиций под ягоды, при этом в каждое место мы можем положить не более одной ягоды. Вычислите, сколькими способами мы можем это сделать. По какому правилу теперь можно посчитать общее количество случаев?

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

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

Выложим в ряд орехи и грибы — сделать это можно $5 C13$ способами. Далее рассмотрим позиции между выложенными орехами и грибами и по краям от них — получим 14 мест для ягод. Остаётся выложить их туда $11 C14$ способами.

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

Сначала объединим орехи и грибы в неягоды, откуда получим 13 неягод и 11 ягод. Далее назовём нейтроном пару (неягода, ягода).

Если на крайней левой позиции в ряду лежит неягода, то 11 ягод образуют нейтроны, поскольку рядом с ними не могут находиться другие ягоды, и левее каждой точно есть неягода. Отсюда имеем 11 нейтронов и 2 дополнительные неягоды. В итоге получаем $2 C13$ способов поставить эту неягоду, то есть 78 расстановок.

Если на крайней левой позиции лежит ягода, то остаются только 10 ягод, каждая из которых попадает в свой нейтрон. Получаем 10 нейтронов и 3 неягоды, откуда имеем $C313 = 286$ расстановок.

Получаем $364= C314$ расстановки. Остаётся вспомнить, что неягоды делятся на два вида. Чтобы учесть это, домножим все способы на $51!3!⋅8!,$ то есть число способов расставить $5$ орехов среди тринадцати неягод, откуда и получаем ответ.

Ответ:

$C5 ⋅C11 13 14$

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

Задача 8#77816

Каким числом способов можно разложить 30 яблок в 3 корзинки так, чтобы в первой корзинке лежало меньше яблок, чем во второй, во второй меньше, чем в третьей, и пустых корзинок не было?

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

Рассмотрим уравнение

a+ b+ c= 30.

Расставим $30$ единиц в ряд, выберем два промежутка между единицами и поставим в них по чёрточке. Число единиц слева от первой чёрточки равно $a$ (число яблок в первой корзине), справа от второй – равно $c$ (число яблок в третьей корзине). Число способов выбрать два промежутка равно $29⋅28-= 406 2$ .

Надо вычесть из этого числа количество случаев, когда среди чисел $a,b,c$ есть равные. Пусть $a =b$ . Тогда $2a+ c= 30$ , это уравнение имеет $14$ ненулевых решений ( $2a$ чётное и может изменяться от $2$ до $28$ ). Аналогично, будет по $14$ случаев, когда $b= c$ или $a =c$ . Итак, $406− 3⋅14 =364$ . Случай $a= b= c$ посчитан один раз в общем числе способов и три раза вычтен, а надо его исключить всего один раз, поэтому требуется прибавить $2$ . Число $364 +2= 366$ равно числу упорядоченных троек различных $a,b,c$ . Но нужен порядок $a< b< c$ , поэтому разделим на число перестановок трёх элементов: $366 6 = 61.$

Ответ: 61

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

Задача 9#74648

Борис раскладывает 8 белых и 8 чёрных шариков по двум коробкам. Настя наугад выбирает коробку, а потом не глядя берёт из неё шарик. Может ли Борис так разложить шарики по двум коробкам, чтобы вероятность вынуть белый шарик была больше $2 3?$