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

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

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

Сосчитаем способы без учёта ограничений на повторы и максимум у Бори. Метод шаров и перегородок даёт способов деления.

Теперь вычтем способы с повторами. Так как 1001 не кратно 3, число орехов может совпасть только у двоих, это число может быть любым от 1 до 500. Для каждого возможного есть 3 способа распределить и орехов между троими. Значит, число способов с повторами равно а без повторов —

Пусть теперь бельчата делят ”случайно”, так, что каждый получает разное число. Однако дальше они распределение ”исправляют” : тот, кто получит больше всех, меняется своей долей с Борей. Тогда одно и то же ”исправленное” распределение получается из трёх ”случайных”: Боря мог получить максимум либо сразу, либо поменявшись с Васей, либо поменявшись с Петей. Тогда ”исправленных” распределений втрое меньше, чем ”случайных”, т.е.

Прибавим единицу к обеим частям и преобразуем уравнение:

Таким образом,

Числа — целые неотрицательные, при этом выполнено

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

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

Предположим, что мы уже купили какие-то открыток. В таких задачах хочется представить объекты в каком-то более удобном виде, например, разложить их в удобном для восприятия виде. Разложим их на столе так, чтобы сначала подряд шли открытки вида, потом подряд открытки вида, затем — открытки вида и наконец открытки вида. Теперь мы видим открыток, между которыми как бы стоят невидимые разделители. Их три штуки: до первого разделителя лежат открытки первого вида, между вторым и третьим — второго вида, от второго и до третьего — третьего вида, а от третьего и до конца — четвертого. Таким образом, мы свели задачу к задаче расставить три разделителя среди открыток.

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

Заметим, что открыток какого-то вида может и не быть вовсе — в этом случае два разделителя стоят рядом. Значит, мы видим следующую модель: нужно выбрать места для разделителей, а остальные места заполнят открытки, причем их вид уже однозначно определяется из расположения разделителей. Для каждого из трех разделителей и открыток есть место, значит, три места для разделителей мы выбираем из мест. У нас способов — выбрать место для первого разделителя, — для второго, для третьего и поделить на так как разделители у нас одинаковые. Тогда ответ:

Разложим на простые множители:

Значит, каждое число в строке имеет вид

Cтроку можно закодировать тройками показателей, первая состоит из 6 показателей степени у двойки с суммой 4, вторая — у тройки с суммой 2, третья — у пятёрки с суммой 1. Методом шаров и перегородок находим, что троек первого вида второго — третьего — Тогда количество строк равно

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

1) Предположим, что мы уже купили какие-то 10 открыток. В таких задачах хочется представить объекты в каком-то более удобном виде, например, разложить их в удобном для восприятия виде. Разложим их на столе так, чтобы сначала подряд шли открытки 1-го вида, потом подряд открытки 2-го вида, в конце — открытки третьего вида. Теперь мы видим 10 открыток, между которыми как бы стоят невидимые разделители. Их две штуки: до первого разделителя лежат открытки первого вида, между вторым и третьим — второго вида, от второго и до конца — третьего вида. Таким образом, мы свели задачу к задаче расставить два разделителя среди 10 открыток.

В данному пункте эти разделители (обычно их называют перегородками, а метод — шары и перегородки) не могут стоять в начале и в конце, а также рядом. Поэтому для первого разделителя есть возможных мест, а для второго — различных мест. Порядок постановки разделителей нам не важен, поэтому ответ .
2) Заметим, что открыток какого-то вида может и не быть вовсе — в этом случае два разделителя стоят рядом. Значит, мы видим следующую модель: нужно выбрать два места для разделителей, а остальные места заполнят открытки, причем их вид уже однозначно определяется из расположения разделителей. Сколько объектов у нас всего? Для каждого из двух разделителей и 10 открыток есть место, значит, два места для разделителей мы выбираем из мест. Сколько таких способов? 12 способов — выбрать место для первого разделителя, 11 — для второго, и поделить на 2, так как разделители у нас одинаковые. Тогда ответ: .

Построим школьников в линию, например, по росту и зафиксируем их порядок. Теперь рассмотрим линию из белых шариков также слева направо по порядку.

На три из позиций между этими шариками поставим столбики-перегородки. Пусть школьники, соответствующие белым шарикам до первой перегородки, пойдут в первую аудиторию. Школьники после первой перегородки и до второй пойдут во вторую аудиторию. Аналогично с третьей аудиторией, и наконец, школьники, белые шарики которых находятся правее последней (третьей) перегородки, направятся в четвёртую аудиторию.

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

Построим школьников в линию, например, по росту и зафиксируем их порядок. Теперь рассмотрим линию из белых шариков также слева направо по порядку.

Ровно 3 шарика закрасим красным цветом. Останется шариков, которые можно поставить в соответствие школьникам в их зафиксированном порядке. Пусть школьники, соответствующие белым шарикам до первого красного в линии, пойдут в первую аудиторию. Школьники, соответствующие белым шарикам после первого красного до следующего красного в линии, пойдут во вторую аудиторию. Аналогично с третьей, и наконец, школьники, белые шарики которых находятся в линии правее последнего (третьего) красного, направятся в четвёртую аудиторию.

Если красные шарики стоят рядом, то в соответствующую аудиторию ни один школьник не сядет. Если красные шарики стоят в начале, то первую аудиторию никто не займёт, если в конце — последнюю никто не займёт.

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

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

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

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

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

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

Распределить шаров на группы — это то же самое, что и расставить перегородки между шарами на мест, причём 2 перегородки могут стоять в одном месте (тогда одна из групп будет пустой). Это можно сделать способами.

Тогда, так как красные и синие шары мы распределяем независимо друг от друга, получаем ответ

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

Расставим единиц в ряд, выберем два промежутка между единицами и поставим в них по чёрточке. Число единиц слева от первой чёрточки равно (число яблок в первой корзине), справа от второй равно (число яблок в третьей корзине). Число способов выбрать два промежутка равно

Надо вычесть из этого числа количество случаев, когда среди чисел есть равные.

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

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

Число равно числу упорядоченных троек различных . Но нужен порядок , поэтому разделим на число перестановок трёх элементов:

Пусть мы как-то выбрали купюр. Выложим их в линию следующим образом: сначала все купюры достоинством в тысячу, потом в тысячи, затем — в тысяч. Заметим, что этому выбору можно однозначно сопоставить способ расставить две перегородки между шарами (если считать купюры шарами).

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

Если перегородки в разных местах, то количество способов равно в противном случае — Значит, итоговый ответ равен

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

Первого человека в тройку возьмём любого из 18. Дальше нужно выбрать второго и третьего. Пусть между первым и вторым при подсчёте по часовой стрелке сидит человек, между вторым и третьим — между третьим и первым —

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

Итак, для каждого из 18 способов выбора первого есть 55 способов однозначно определить оставшихся двух людей. Но по условию задачи нас спрашивали количество троек без различия, кто в этой тройке первый. Поэтому нужно поделить на , ведь каждую тройку мы посчитали по три раза, когда какой-то человек являлся в ней первым.

_________________________________________________________________________________________________________________________________________________________________________________

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

Пронумеруем места за столом по часовой стрелке от до

Посчитаем, сколько троек мы можем создать, если один из людей сидит на первом месте.

В этом случае мы не сможем взять людей, сидящих на и местах. То есть следующего мы сможем выбрать только способами. Если следующим мы выбираем человека, сидящего на месте, то следующего можно выбрать с по место, то есть способами; если вторым выбираем человека на месте, то третьего можно выбрать способами и т.д.

В итоге, если один из выбранных людей сидит на первом месте, то существует способов подобного выбора.

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

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

Выдадим каждому гному по камней, а оставшиеся камня выложим в ряд. Чтобы разделить оставшиеся камни между гномами, достаточно расположить на места между камнями два разделителя. Глоин получит камни левее первого разделителя, Оин – камни между двумя разделителями, а Траин – камни правее второго разделителя. Число способов расположить эти два разделителя равно

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

Итак, нужно понять, какому соответствует большее число троек таких что

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

Количество способов поставить перегородки равно (возрастающая функция от ).

При при подсчёте мы получим различные перестановок тройки которые не соответствуют условию . При получим различные перестановки тройки и перестановок тройки которые не соответствуют условию

Итак, подходящих троек при будет при их при их

Наибольшая вероятность достигается при и

Нужно найти, сколькими способами можно решить уравнение

где

Выпишем в ряд десять единиц и поставим между ними две перегородки (в разные места). Тогда это число единиц до левой перегородки, — между левой и правой, — после правой. Так как единиц всего , то . Заметим, что мест для расположения перегородок всего , а нам нужно выбрать только . Поэтому число решений уравнения равно Всего есть способов выбрать числа из . Значит итоговая вероятность равна

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

Пусть шары — это саквояжи. Перегородки между ними — разбиение саквояжей по цветам. Рассмотрим случаи:

В первом случае в покупку входят саквояжи всех четырех цветов. Тогда поставим между шарами перегородки: число шаров, лежащих слева от первой перегородки, равно числу саквояжей первого цвета; число шаров, лежащих между первой и второй — второму и т.д. Мест для перегородок поэтому в этом случае получаем способов.

Во втором случае в покупке присутствуют саквояжи трёх из четырех цветов. Выбрать их способа. Ставим перегородки на мест — способов. Итого в этом случае получаем способов.

В третьем случае в покупку входят саквояжи двух цветов. Есть их выбрать. Затем ставим одну перегородку между шарами: способов. Итого в этом случае получаем

В четвертом случае в покупку входят саквояжи только одного цвета. Есть способа его выбрать

Суммируя способы во всех случаях, получаем

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

Старуха Шапокляк может взять школьную тетрадку в клетку и отметить там ряд из клеток. Затем в произвольных разных клетках этого ряда она ставит крестики. Передав этот листок продавцу, она ставит условие: число клеток, лежащее слева от первого крестика, равно числу саквояжей первого цвета; число клеток, лежащих между первым и вторым крестиком, равно числу саквояжей второго цвета, число клеток, лежащее правее третьего крестика, равно числу саквояжей -ого цвета. При этом, если левее первого крестика, между какими-либо двумя крестиками, или правее -го крестика нет клеток, значит, в покупке не будет саквояжей соответствующего цвета.

Тем самым число вариантов покупки равно числу способов расстановки крестика на различных позициях, то есть равно

Выдадим каждому пирату по монет, а оставшиеся монет выложим в ряд. Чтобы разделить оставшиеся монеты между пиратами, достаточно расположить на местах между монетами две перегородки. Тем самым, Джо получит монеты левее первой перегородки, Билл монеты между двумя перегородками, а Том - монеты правее второй перегородки. Число способов расположить эти перегородки: .