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

Количество способов, исходов, слагаемых → .07 Метод шаров и перегородок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 21#70306Максимум баллов за задание: 7

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

Источники: Физтех - 2014, 10 класс

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

Подсказка 1

Частая ошибка в такой задаче — забыть, что первая цифра не может равняться нулю! Давайте это не забудем и сразу поставим на первое место цифру, которая не равна нулю. Тогда на оставшихся 22 местах надо расположить 7 единичек, как это можно сделать?

Подсказка 2

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

Подсказка 3

Верно, это метод шаров и перегородок! То есть, расположим в ряд 22 места и 7 единичек, то есть, всего есть 29 мест, куда можно поставить единичку! А нам нужно выбрать 7 мест.

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

Распределим между $23$ разрядами $7$ “единичек”, так как на первом разряде точно стоит хотя бы одна “единичка”. Ставим $22$ перегородки между $7$ шарами. Так как порядок выбора мест не важен, число способов: $29⋅28⋅27⋅26⋅25⋅24⋅23- 7!$

Ответ:

$29⋅28⋅27⋅26⋅25⋅24⋅23 7!$

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

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

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

Задача 22#70307Максимум баллов за задание: 7

У Игоря Горшкова есть все семь книг про Гарри Поттера. Сколькими способами Игорь может расставить эти семь томов на три различные книжные полки так, чтобы на каждой полке стояла хотя бы одна книга? (Расстановки, которые отличаются порядком книг на полке, считаются различными.)

Источники: ПВГ - 2014, 9 класс

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

Подсказка 1

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

Подсказка 2

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

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

Сначала определим порядок между книгами, а потом разделим их двумя перегородками на 3 непустых множества (будем рассматривать всевозможные разбиения данного набора книг), например

12|345|67 или 123|45|67 или 1|23|4567

Первое множество положим на первую полку, второе — на вторую, третье — на третью. Расставить книги в ряд можно $7!$ способами, для перегородок между книгами $6$ мест, тогда количество способов расставить две перегородки равно $6⋅5. 2$ Получим

6⋅5 7!⋅ 2 =75600

Ответ: 75600

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

Задача 23#80164Максимум баллов за задание: 7

В классе $12$ учеников. Их нужно разбить на две группы (первую и вторую), состоящие из чётного числа учеников. Сколькими способами это можно сделать?

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

Подсказка 1

Во-первых, в условии сделан акцент на то, что группы имеют номера, то есть порядок групп нам важен. Начнём с малого. Как посчитать количество способов выбрать в первую группу двух учеников, а во вторую 10?

Подсказка 2

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

Подсказка 3

Верно, с помощью числа сочетаний. То есть этих способов ровно C из 12 по 2. Теперь, по аналогии, осталось посчитать сколько способов выбрать 4 из 12, 6 из 12, 8 из 12 и 10 из 12.

Подсказка 4

Делаем это также с помощью числа сочетаний!

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

Если в первой группе $2x$ человек, $x∈ [1;5],$ то количество способов разбиения учеников в этом случае равно $C2x 12$ (выбрали $2x$ человек в одну группу, остальных — во вторую). Значит, чтобы получить ответ, нужно просуммировать полученную цешку при $x ∈[1;5]:$

2 4 6 8 10 2 4 6 C12+ C12+C12+ C12+ C12 = 2(C12+ C12)+ C12 = 2046

Ответ:

$C2 + C4 +C6 +C8 + C10= 2046 12 12 12 12 12$

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

Задача 24#39645Максимум баллов за задание: 7

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

Источники: Физтех-2011, отборочный тур, 9 (см. fizteh2013.ru)

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

Подсказка 1

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

Подсказка 2

Верно, если за 1, 2, 3, 4 и 5 кандидата проголосуют соответственно a, b, c, d и e депутатов, то их сумма будет равна 19. И того, учитывая ограничения на количество голосов(проголосовавших депутатов) нам нужно найти количество таких пятёрок. Тогда с точки зрения шаров и перегородок, что нам нужно сделать?

Подсказка 3

Да, нам нужно расставить 4 перегородки в какое-то количество мест. Поймём теперь в какое. Надо не забыть, что перегородки могут стоять в начале и в конце(когда за кандидата никто не проголосовал, например) и рядом между собой(тогда за кандидата между ними 0 голосов). Итого у нас получается всего элементов 23 – это 20 мест для одной перегородки между шарами и по краям, но у нас ещё есть 3 перегородки, которые могут стоять рядом с нашими позициями, то есть ещё дополнительных 3 места.

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

Количество различных протоколов соответствует количеству различных упорядоченных пятёрок $(x ,x ,x ,x,x ) 1 2 3 4 5$ , таких что $x1+ x2+ x3+x4+ x5 = 19$ с учётом того, что у нас есть ограничения $x1 ≤ 19,x2 ≤ 19,x3 ≤ 19,x4 ≤19,x5 ≤19.$

Такая задача эквивалентна тому, чтобы расставить $4$ перегородки между $19$ шариками, причем перегородки могут стоять в начале, в конце или на одной и той же позиции (так как голосов каждого вида может быть любое количество от $0$ до $19$ , то есть ограничения на количество голосов, кроме уравнения - связки, у нас нет). Количество элементов в каждой из получившихся пяти группах между перегородками (возможно, каких-то пустых) это и будут значения $x1,x2,x3,x4,x5.$

Итак, у нас есть $23$ элемента - $19$ шариков и $4$ перегородки. Количество различных (!) их перестановок равно $4 C 23.$

Ответ:

$8855$

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

Задача 25#70308Максимум баллов за задание: 7

26 солдат выстроены в одну шеренгу. Сколько существует различных способов выбрать 11 из них так, что никакие двое из них не стоят рядом?

Источники: Физтех - 2011, 10 класс

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

Подсказка 1

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

Подсказка 2

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

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

Используем метод шаров и перегородок. Шары — не выбранные солдаты, а перегородки — выбранные. При этом перегородки не могут стоять рядом, но могут стоять в начале и конце. Подсчитаем количество способов: первую перегородку между $15$ шарами ставим на любое из $16$ мест, вторую на оставшиеся $15$ мест и так далее, последнюю перегородку ставим на одно из $6$ мест. Так как порядок выбора мест не важен, число способов:

16 ⋅15⋅14⋅...⋅6 -----11!------=4368

Ответ: 4368

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

Задача 26#115887Максимум баллов за задание: 7

Перед чемпионатом мира по футболу тренер сборной России решил провести три тренировочных матча (каждый продолжительностью $90$ минут) с участием семи игроков, чтобы оценить их навыки. В любой момент времени во время матча на поле находится ровно один из них. Суммарное время (измеряемое в минутах), проведённое на поле каждым из четырёх первых игроков, должно быть кратно $7,$ а для каждого из трех оставшихся — кратно $13.$ Количество замен игроков во время каждого матча не ограничено. Сколько существует возможных распределений игрового времени между игроками при заданных условиях?

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

Пусть $x i$ $(i=1,2,...,7)$ — время $i$ -го игрока на поле. Требуется найти количество наборов натуральных чисел, удовлетворяющих уравнению:

x1+x2+ ...+ x7 = 270

при условиях: $xi ... 7 (i= 1,2,3,4), xj ... 13 (j = 5,6,7)$

Положим:

x1 +x2+ x3+ x4 = 7m, x5+ x6+x7 =13n.

Тогда:

7m + 13n = 270,

где $m, n∈ ℕ,$ $m ≥ 4,$ $n ≥3.$

Найдём все пары натуральных чисел $(m, n),$ удовлетворяющие уравнению:

(m,n)= (33,3), (20,10), (7,17)

Случай 1: $(m,n)= (33,3)$

Здесь $x5 = x6 = x7 = 13.$ Положим $xi =7yi$ ( $i= 1,2,3,4),$ тогда:

y1+ y2+ y3 +y4 = 33

Количество решений по методу шаров и перегородок:

C43−31−1 = C332 = 4960

Случай 2: $(m,n)= (20,10)$

Положим $xi = 7yi$ ( $i= 1,2,3,4$ ) и $xj = 13yj$ ( $j = 5,6,7).$ Тогда:

y1+ y2 +y3+ y4 =20, y5+ y6+ y7 =10

Количество решений по методу шаров и перегородок:

4−1 7−1 C20−1⋅C10− 1 = C319 ⋅C29 = 34884

Случай 3: $(m,n)= (7,17)$

Аналогично:

y1+ y2+ y3 +y4 = 7, y5+ y6 +y7 = 17

Количество решений по методу шаров и перегородок:

C4−1⋅C7−1 = C3⋅C2 = 2400 7−1 17−1 6 16

Общее количество допустимых распределений:

4960+34884+2400= 42244

Ответ:

$42244$

Курсы

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

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

Задача 27#120512Максимум баллов за задание: 7

Инвестор намеревается купить 12 акций 4 компаний (не менее чем по одной акции каждой). Сколькими способами он может распределить свой капитал?

A: $4 C12$

Б: $3 C11$

B: $3 C13$

Г: $12 4$

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

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

Ответ: Б

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

Задача 28#120513Максимум баллов за задание: 7

Инвестор намеревается купить 11 акций 5 компаний (причем от покупки акций одной или более из этих компаний он может отказаться). Сколькими способами он может распределить свой капитал?

A: $4 C15$

Б: $5 C15$

B: $4 C16$

Г: $5 C 16$

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

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

Ответ: А

Предыдущая подтема

Следующая подтема