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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 6#69404

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

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

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

Подсказка 1

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

Подсказка 2

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

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

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

Ответ: 144

Курсы

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

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

Задача 7#69407

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

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

Подсказка 1

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

Подсказка 2

Разница между количеством очков команд на первом и на последнем месте хотя бы 2. А могло ли быть такое, что "Метеор" совсем никого не обыграл?

Подсказка 3

"Метеор" обязательно кого-то обыграет, так как иначе у него будет набрано не более половины всех очков. Можно ли провести аналогичные рассуждения про "Бельчат"?

Подсказка 4

Чтобы уменьшение баллов за победу дало "Бельчатам" попасть на последнее место, у них поражений должно быть больше, чем побед! Тогда давайте проследим, как сильно могли измениться баллы "Метеора"? Сколько и каких игр нужно "Бельчонку", чтобы в любом случае упасть ниже соперников?

Подсказка 5

После пересчёта "Метеор" потеряет хотя бы одно очко, тогда несложно посчитать, сколько же очков должны потерять "Бельчата", чтобы условие выполнилось! Не забудьте построить пример ;)

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

Оценка: До пересчёта у команды «Бельчата» было хотя бы на 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$

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

Задача 8#74648

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

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

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

Подсказка 1

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

Подсказка 2

Положим один белый шарик в одну из коробок!

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

Борис положит в первую коробку 1 белый шарик, а во вторую все остальные. Тогда вероятность вынуть белый шарик равна

1 1 7 22 2 2 + 2 ⋅15-= 30 > 3

Ответ: да

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

Задача 9#77816

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

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

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

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

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

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

Задача 10#94777

Дана квадратная таблица $n× n$ , где $n≥ 2$ . В каждую из некоторых $k$ клеток таблицы ставится по одной фишке так, чтобы в любом квадрате $2 ×2$ было ровно 2 фишки. Найдите все значения $k$ , при которых это можно сделать.

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

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

Подсказка 1

Разберите случаи чётного и нечётного n. Попробуйте разбить доску на такие фигурки, в которых мы можем оценить количество фишек!

Подсказка 2

В случае чётного n несложно разбить на квадраты 2 на 2 и оценить общее количество фишек! Но что делать в случае нечётного n? Если мы попробуем разбить на квадраты, то в правом нижнем углу образуется уголок шириной в 1 клетку, в котором мы не сможем явно оценить количество фишек. А если попробовать "затронуть" эту полоску, примыкающую к квадратам?

Подсказка 3

Обратите внимание на полоски площадью 2, примыкающие к квадратам 2 на 2 справа и снизу? Сколько в них должно быть фишек? А что если попробовать скомбинировать в разбиении такие фигуры и квадраты?

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

Если $n = 2m$ — четное число, то вся таблица разбивается на $m2 = n2 4$ квадратов $2× 2$ , в каждом из которых находится ровно 2 фишки. Поэтому общее число фишек равно $2 n2- 2m = 2$ .

Пусть теперь $n= 2m +1$ . Разобьем таблицу на квадраты $2× 2$ и фигуры вида:

$PIC$

так, как показано на рисунке:

$PIC$

В любой такой фигуре должна стоять хотя бы одна фишка, иначе в квадрате $2× 2$ , примыкающем к данной, должно быть не менее 3 фишек — противоречие.

$PIC$

Таким образом, общее число фишек в таблице не менее $2m2+ m$

С другой стороны, поскольку в любом квадрате $2× 2$ должно быть ровно 2 пустых клетки (незанятых фишками), то аналогично получаем, что пустых клеток в таблице также не менее $2m2 +m$ . И зн̆ачит, фишек в таблице не более