Метод шаров и перегородок
Ошибка.
Попробуйте повторить позже
На прямой отмечено точек. Сколькими способами из них можно выбрать
точек так, чтобы никакие две выбранные точки не были
соседними?
Заметим, что НЕ отмеченных точек у нас отмеченные точки мы можем ставить во все
промежутков между ними и ещё в
места
по краям, значит всего нужно выбрать
вариантов из
Ошибка.
Попробуйте повторить позже
В почтовом отделении продаются открытки 3 видов. Сколькими способами можно купить в нем 10 открыток, если 1) нужно купить хотя бы по одной открытке каждого вида; 2) какие-то виды можно вообще не покупать?
1) Предположим, что мы уже купили какие-то 10 открыток. В таких задачах хочется представить объекты в каком-то более удобном виде, например, разложить их в удобном для восприятия виде. Разложим их на столе так, чтобы сначала подряд шли открытки 1-го вида, потом подряд открытки 2-го вида, в конце — открытки третьего вида. Теперь мы видим 10 открыток, между которыми как бы стоят невидимые разделители. Их две штуки: до первого разделителя лежат открытки первого вида, между вторым и третьим — второго вида, от второго и до конца — третьего вида. Таким образом, мы свели задачу к задаче расставить два разделителя среди 10 открыток.
В данному пункте эти разделители (обычно их называют перегородками, а метод — шары и перегородки) не могут стоять в начале и в
конце, а также рядом. Поэтому для первого разделителя есть возможных мест, а для второго —
различных мест. Порядок постановки
разделителей нам не важен, поэтому ответ
.
2) Заметим, что открыток какого-то вида может и не быть вовсе — в этом случае два разделителя стоят рядом. Значит, мы видим
следующую модель: нужно выбрать два места для разделителей, а остальные места заполнят открытки, причем их вид уже однозначно
определяется из расположения разделителей. Сколько объектов у нас всего? Для каждого из двух разделителей и 10 открыток есть место,
значит, два места для разделителей мы выбираем из мест. Сколько таких способов? 12 способов — выбрать
место для первого разделителя, 11 — для второго, и поделить на 2, так как разделители у нас одинаковые. Тогда ответ:
.
Ошибка.
Попробуйте повторить позже
Для проведения олимпиады преподаватели разбивают школьников следующим образом: список в алфавитном порядке разбивается на
части, первая идет в первую аудиторию, вторая — во вторую и т. д. При этом в каждую аудиторию отправляется хотя бы один
школьник. Сколькими способами можно произвести распределение?
Построим школьников в линию, например, по росту и зафиксируем их порядок. Теперь рассмотрим линию из белых шариков также
слева направо по порядку.
На три из позиций между этими шариками поставим столбики-перегородки. Пусть школьники, соответствующие белым шарикам до
первой перегородки, пойдут в первую аудиторию. Школьники после первой перегородки и до второй пойдут во вторую аудиторию.
Аналогично с третьей аудиторией, и наконец, школьники, белые шарики которых находятся правее последней (третьей) перегородки,
направятся в четвёртую аудиторию.
В итоге получили вариант рассадки школьников по аудиториям. Каждой расстановке
перегородок на
мест между шариками
соответствует одна из рассадок. Других нет. Поэтому всевозможные способы рассадки определяются количеством способов выбрать
места
из
Это количество равно
Ошибка.
Попробуйте повторить позже
Для проведения олимпиады преподаватели разбивают школьников следующим образом: список в алфавитном порядке разбивается на
части, первая идет в первую аудиторию, вторая — во вторую и т. д. (некоторые аудитории могут остаться пустыми). Сколькими
способами можно произвести рассадку?
Построим школьников в линию, например, по росту и зафиксируем их порядок. Теперь рассмотрим линию из белых шариков также
слева направо по порядку.
Ровно 3 шарика закрасим красным цветом. Останется шариков, которые можно поставить в соответствие школьникам в их
зафиксированном порядке. Пусть школьники, соответствующие белым шарикам до первого красного в линии, пойдут в первую аудиторию.
Школьники, соответствующие белым шарикам после первого красного до следующего красного в линии, пойдут во вторую аудиторию.
Аналогично с третьей, и наконец, школьники, белые шарики которых находятся в линии правее последнего (третьего) красного, направятся
в четвёртую аудиторию.
Если красные шарики стоят рядом, то в соответствующую аудиторию ни один школьник не сядет. Если красные шарики стоят в начале, то первую аудиторию никто не займёт, если в конце — последнюю никто не займёт.
В итоге получили вариант рассадки школьников по аудиториям. Каждой раскраске
шариков из
в красный цвет соответствует
одна из рассадок. Других нет. Поэтому всевозможные способы рассадки определяются количеством способов выбрать
шарика из
на
покраску. Это количество равно
Ошибка.
Попробуйте повторить позже
15 депутатов выбирают председателя из 3 достойных кандидатур. Сколькими способами могут распределиться голоса, если каждый депутат голосует ровно за одну кандидатуру и учитывается лишь количество голосов, поданных за каждую кандидатуру?
Выстроим 15 шариков в ряд и будем ставить между ними две перегородки. Количество шариков до первой перегородки будет
соответствовать количеству голосов за первую кандидатуру, между первой и второй перегородкой — за вторую кандидатуру, оставшиеся —
за третью. Если перегородки стоят в одном промежутке, то за вторую кандидатуру никто не проголосовал — таких вариантов
Если же две перегородки стоят в двух разных местах между шариками (по краям тоже могут быть, поэтому всего 16 позиций), то способов
их поставить
Ошибка.
Попробуйте повторить позже
В довольно большом кошельке депутата лежит по купюр достоинством в
тысяч рублей. Сколькими способами можно из этих
купюр выбрать
Купюры одного достоинства одинаковые.
Нам нужно выбрать купюр, пусть из них
номиналом в
рублей,
— номиналом в
тысячи рублей,
— номиналом в
тысяч рублей. Нужно понять, сколько есть способов выбрать такие тройки
, что
с учётом того, что у нас есть
ограничения
Такая задача эквивалентна тому, чтобы расставить перегородки между
шариками, причем перегородки могут
стоять в начале, в конце или на одной и той же позиции (так как каждого вида купюр может быть любое количество от
до
, а каждого номинала имеется в достаточном количестве, то есть ограничения на количества купюр каждого
вида у нас нет). Количество элементов в каждой из получившихся трёх групп (возможно, пустых) это и будут значения
Имеем способов поставить две перегородки на разные позиции и ещё
способов поставить две перегородки в одно и то же место
(это соответствует разбиению на сумму с нулём купюр одного из номиналов или даже двух, если все шары находятся по одну сторону от
перегородок). Итого
.
Ошибка.
Попробуйте повторить позже
Сколькими способами можно представить в виде произведения трёх натуральных чисел, если произведения, отличающиеся порядком
множителей, считаются различными?
Разложим число на множители:
значит, каждый множитель имеет вид:
где
Следовательно,
нам нужно распределить
двоек и
пятерок на три множителя, то есть как будто распределить
красных шаров и
синих шаров
на
группы.
Распределить шаров на
группы — это то же самое, что и расставить
перегородки между
шарами на
мест, причём 2
перегородки могут стоять в одном месте (тогда одна из групп будет пустой). Это можно сделать
способами.
Тогда, так как красные и синие шары мы распределяем независимо друг от друга, получаем ответ
Ошибка.
Попробуйте повторить позже
Каким числом способов можно разложить 30 яблок в 3 корзинки так, чтобы в первой корзинке лежало меньше яблок, чем во второй, во второй меньше, чем в третьей, и пустых корзинок не было?
Источники:
Рассмотрим уравнение
Расставим единиц в ряд, выберем два промежутка между единицами и поставим в них по чёрточке. Число единиц слева от первой
чёрточки равно
(число яблок в первой корзине), справа от второй равно
(число яблок в третьей корзине). Число способов выбрать два
промежутка равно
Надо вычесть из этого числа количество случаев, когда среди чисел есть равные.
Пусть . Тогда
, это уравнение имеет
ненулевых решений (
чётное и может изменяться от
до
).
Аналогично будет по
случаев, когда
или
Итак, . Случай
посчитан один раз в общем числе способов и три раза вычтен, а надо его исключить всего
один раз, поэтому требуется прибавить
Число равно числу упорядоченных троек различных
. Но нужен порядок
, поэтому разделим на число
перестановок трёх элементов:
Ошибка.
Попробуйте повторить позже
В кошельке лежит по купюр достоинством в
тысяч рублей. Сколькими способами можно из этих
монет выбрать
Купюры одного достоинства одинаковые.
Пусть мы как-то выбрали купюр. Выложим их в линию следующим образом: сначала все купюры достоинством в
тысячу, потом в
тысячи, затем — в
тысяч. Заметим, что этому выбору можно однозначно сопоставить способ расставить две перегородки между
шарами (если считать купюры шарами).
Следовательно, нужно посчитать количество расстановок двух перегородок между двумя шарами, если перегородки могут стоять перед первым шаром или после последнего и в одном месте могут быть две перегородки.
Если перегородки в разных местах, то количество способов равно в противном случае —
Значит, итоговый ответ равен
Ошибка.
Попробуйте повторить позже
За круглым столом разместились человек. Сколькими способами можно выбрать из этих людей троих, чтобы между любыми двумя из
выбранных людей находилось бы еще по меньшей мере два человека?
Первое решение.
Первого человека в тройку возьмём любого из 18. Дальше нужно выбрать второго и третьего. Пусть между первым и
вторым при подсчёте по часовой стрелке сидит человек, между вторым и третьим —
между третьим и первым —
По условию должно выполняться При этом
(если 3 человека выбрано, то 15 не выбраны). Если
уменьшить каждую из переменных на единицу, то получаем уже уравнение в натуральных числах
По методу шаров и
перегородок оно имеет
решений.
Итак, для каждого из 18 способов выбора первого есть 55 способов однозначно определить оставшихся двух людей. Но по условию задачи
нас спрашивали количество троек без различия, кто в этой тройке первый. Поэтому нужно поделить на
, ведь каждую тройку мы
посчитали по три раза, когда какой-то человек являлся в ней первым.
_________________________________________________________________________________________________________________________________________________________________________________
Второе решение.
Пронумеруем места за столом по часовой стрелке от до
Посчитаем, сколько троек мы можем создать, если один из людей сидит на первом месте.
В этом случае мы не сможем взять людей, сидящих на и
местах. То есть следующего мы сможем выбрать только
способами. Если следующим мы выбираем человека, сидящего на
месте, то следующего можно выбрать с
по
место, то есть
способами; если вторым выбираем человека на
месте, то третьего можно выбрать
способами и
т.д.
В итоге, если один из выбранных людей сидит на первом месте, то существует способов подобного
выбора.
Общее количество выбора троих людей указанным в условии способом равно:
Отметим, что после умножения на общее число людей, необходимо разделить на
так как в каждой тройке можно начинать выбор
с любого из трех людей.
Ошибка.
Попробуйте повторить позже
Гномы Глоин, Оин и Траин нашли одинаковых драгоценных камней и хотят разделить их между собой так, что каждый из них получит
не менее
камней. Сколькими способами гномы смогут это сделать?
Источники:
Выдадим каждому гному по камней, а оставшиеся
камня выложим в ряд. Чтобы разделить оставшиеся камни между гномами,
достаточно расположить на
места между камнями два разделителя. Глоин получит камни левее первого разделителя, Оин – камни
между двумя разделителями, а Траин – камни правее второго разделителя. Число способов расположить эти два разделителя равно
Ошибка.
Попробуйте повторить позже
Игральная кость представляет собой кубик, на гранях которого отмечено от одного до шести очков. Петя случайным образом бросает на
стол три игральных кости одновременно и считает сумму числа очков, выпавших на всех костях. Каждое значение этой суммы,
расположенное от
до
может появится с определенной вероятностью. Найти
при котором эта вероятность максимально
возможная.
Заметим, что вероятность получить значение такая же, как и вероятность получить значение
ведь соответствующие исходы для
и
можно разделить соответственно на пары троек
где
— число, выпавшее на
-ом
кубике, и
Поэтому рассмотрим значения
в пределах от
до
а для
вероятность будет такая
же.
Итак, нужно понять, какому соответствует большее число троек
таких что
Поставим в ряд шаров, между ними будет
позиций, куда мы будем ставить перегородки (на одну и ту же позицию ставить
перегородки не разрешается). Количество шаров между перегородками и будет соответстовать
Количество способов поставить перегородки равно (возрастающая функция от
).
При при подсчёте мы получим
различные перестановок тройки
которые не соответствуют условию
. При
получим
различные перестановки тройки
и
перестановок тройки
которые не соответствуют условию
Итак, подходящих троек при будет
при
их
при
их
Наибольшая вероятность достигается при
и
Ошибка.
Попробуйте повторить позже
Из множества 1, 2, …, 10 выбираются равновероятно три числа (возможно одинаковых). Какова вероятность того, что сумма этих чисел равна 10?
Источники:
Нужно найти, сколькими способами можно решить уравнение
где
Выпишем в ряд десять единиц и поставим между ними две перегородки (в разные места). Тогда это число единиц до левой
перегородки,
— между левой и правой,
— после правой. Так как единиц всего
, то
. Заметим, что мест для
расположения перегородок всего
, а нам нужно выбрать только
. Поэтому число решений уравнения равно
Всего есть
способов выбрать
числа из
. Значит итоговая вероятность равна
Ошибка.
Попробуйте повторить позже
Старуха Шапокляк решила обзавестись коллекцией из 50 саквояжей. В магазине ей на выбор предложили оранжевые, зелёные, фиолетовые и голубые саквояжи. Сколькими способами она может сделать покупку? Саквояжи одного цвета считаются идентичными.
Источники:
Первое решение.
Пусть шары — это саквояжи. Перегородки между ними — разбиение саквояжей по цветам. Рассмотрим случаи:
В первом случае в покупку входят саквояжи всех четырех цветов. Тогда поставим между шарами
перегородки: число шаров,
лежащих слева от первой перегородки, равно числу саквояжей первого цвета; число шаров, лежащих между первой и второй — второму и
т.д. Мест для перегородок
поэтому в этом случае получаем
способов.
Во втором случае в покупке присутствуют саквояжи трёх из четырех цветов. Выбрать их способа. Ставим
перегородки на
мест —
способов. Итого в этом случае получаем
способов.
В третьем случае в покупку входят саквояжи двух цветов. Есть их выбрать. Затем ставим одну перегородку между
шарами:
способов. Итого в этом случае получаем
В четвертом случае в покупку входят саквояжи только одного цвета. Есть способа его выбрать
Суммируя способы во всех случаях, получаем
Второе решение.
Старуха Шапокляк может взять школьную тетрадку в клетку и отметить там ряд из клеток. Затем в произвольных
разных
клетках этого ряда она ставит крестики. Передав этот листок продавцу, она ставит условие: число клеток, лежащее слева от первого
крестика, равно числу саквояжей первого цвета; число клеток, лежащих между первым и вторым крестиком, равно числу саквояжей
второго цвета, число клеток, лежащее правее третьего крестика, равно числу саквояжей
-ого цвета. При этом, если левее первого
крестика, между какими-либо двумя крестиками, или правее
-го крестика нет клеток, значит, в покупке не будет саквояжей
соответствующего цвета.
Тем самым число вариантов покупки равно числу способов расстановки крестика на
различных позициях, то есть равно
Ошибка.
Попробуйте повторить позже
Три пирата Джо, Билл и Том нашли клад, содержащий 80 одинаковых золотых монет, и хотят разделить их так, чтобы каждому из них досталось не менее 15 монет. Сколько существует способов это сделать?
Источники:
Выдадим каждому пирату по монет, а оставшиеся
монет выложим в ряд. Чтобы разделить оставшиеся монеты между пиратами,
достаточно расположить на
местах между монетами две перегородки. Тем самым, Джо получит монеты левее первой перегородки, Билл
монеты между двумя перегородками, а Том - монеты правее второй перегородки. Число способов расположить эти перегородки:
.
Ошибка.
Попробуйте повторить позже
Сколько существует 23-значных чисел, сумма цифр которых равна восьми?
Источники:
Распределим между разрядами
“единичек”, так как на первом разряде точно стоит хотя бы одна “единичка”. Ставим
перегородки между
шарами. Так как порядок выбора мест не важен, число способов:
Ошибка.
Попробуйте повторить позже
У Игоря Горшкова есть все семь книг про Гарри Поттера. Сколькими способами Игорь может расставить эти семь томов на три различные книжные полки так, чтобы на каждой полке стояла хотя бы одна книга? (Расстановки, которые отличаются порядком книг на полке, считаются различными.)
Источники:
Расставим книги в ряд способами, так как все они различны. Чтобы распределить книги по трем полкам, поставим две перегородки
между 7 шарами. Кол-во способов расставить перегородки:
, итого
Ошибка.
Попробуйте повторить позже
В классе учеников. Их нужно разбить на две группы (первую и вторую), состоящие из чётного числа учеников. Сколькими способами
это можно сделать?
Если в первой группе человек,
то количество способов разбиения учеников в этом случае равно
(выбрали
человек
в одну группу, остальных — во вторую). Значит, чтобы получить ответ, нужно просуммировать полученную цешку при
Ошибка.
Попробуйте повторить позже
депутатов Городского Собрания выбирают Председателя из
кандидатов. Каждый голосует ровно за одного из них. После
голосования составляется протокол заседания, в котором указывается лишь количество голосов за каждого кандидата (без указания, кто за
кого проголосовал). Сколько различных протоколов может получиться?
Источники:
Количество различных протоколов соответствует количеству различных упорядоченных пятёрок , таких что
с учётом того, что у нас есть ограничения
Такая задача эквивалентна тому, чтобы расставить перегородки между
шариками, причем перегородки могут стоять в начале, в
конце или на одной и той же позиции (так как голосов каждого вида может быть любое количество от
до
, то есть ограничения на
количество голосов, кроме уравнения - связки, у нас нет). Количество элементов в каждой из получившихся пяти группах между
перегородками (возможно, каких-то пустых) это и будут значения
Итак, у нас есть элемента -
шариков и
перегородки. Количество различных (!) их перестановок равно
Ошибка.
Попробуйте повторить позже
26 солдат выстроены в одну шеренгу. Сколько существует различных способов выбрать 11 из них так, что никакие двое из них не стоят рядом?
Источники:
Используем метод шаров и перегородок. Шары — не выбранные солдаты, а перегородки — выбранные. При этом перегородки не могут стоять
рядом, но могут стоять в начале и конце. Подсчитаем количество способов: первую перегородку между шарами ставим на любое из
мест, вторую на оставшиеся
мест и так далее, последнюю перегородку ставим на одно из
мест. Так как порядок выбора мест не
важен, число способов: