Метод перегородок

Рассмотрим задачу, в которой нам понадобятся так называемые перегородки.

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

Решение

Для начала, как обычно, попробуем решить задачу перебором по возрастанию. Пусть количество сундуков у первого пирата обозначается первой цифрой в четырехзначном числе, количество сундуков у второго пирата — второй цифрой и так далее. В сумме цифры нашего числа должны давать общее количество сундуков, то есть $6$. В процессе перебора мы, можно сказать, "перекладываем" сундуки от одного пирата к другому:

$1113$ $1122$
$1131$ $1212$
$1221$ $1311$
$2112$ $2121$
$2211$ $3111$

Теперь становится видна особенность нашей задачи. А именно, цифры в нашем числе могут повторяться. Рассмотрим идею, которая поможет решить нам эту задачу, не прибегая к перебору. Расположим все шесть сундуков в ряд. Чтобы разделить их между четырьмя пиратами, нужно провести три перегородки. Например, вот такое расположение перегородок

Честные пираты

будет означать, что первый пират забирает себе три сундука, а остальные — по одному сундуку. Это число $3111$ в нашем переборе. Заметим, что существует всего пять мест для перегородок между шестью сундуками (они отмечены зеленым на рисунке). Из этих пяти мест нам нужно выбрать три места для перегородок. Первую перегородку можно поставить на пять мест, вторую — на четыре места, а третью — на любое из трех оставшихся мест. По правилу умножения имеем $5 \cdot 4 \cdot 3 = 60$ способов поставить перегородки с учетом порядка расстановки. Нам не важно, в каком порядке будут расставлены перегородки, важен только результат. Три перегородки можно переставить $3 \cdot 2 \cdot 1 = 6$ способами. По правилу деления общее число способов разделить сундуки между "честными" пиратами равно $$\dfrac{60}{6} = 10.$$

Ответ: $10$.

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

Сколькими способами четыре пирата могут разделить пять сундуков с золотом, если при этом каждый должен получить целое число сундуков, и пираты "нечестные", то есть некоторые могут остаться и вовсе без добычи?

Решение

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

Нечестные пираты

будет означать, что первому и второму пирату досталось по одному сундуку, третий не получил ничего, а четвертый забрал оставшиеся три сундука. Поступим следующим образом. В нашем ряду должно стоять восемь предметов: пять сундуков и три перегородки. Зарезервируем эти восемь мест (они отмечены зеленым на рисунке), а после выберем из них три места для перегородок. Число способов выбрать три места из восьми равно $$\dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56.$$

Ответ: $56$.

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

Сколько существует способов разбить число $10$ на три натуральных слагаемых? Разбиения, отличающиеся только порядком слагаемых, например, $10 = 1 + 2 + 7$ и $10 = 7 + 2 + 1$ будем считать различными.

Решение

Число $10$ можно представить себе, как сумму из десяти единиц. Нам нужно разбить этот набор единиц на три группы; для этого потребуется две перегородки. Причем в каждой группе должна быть хотя бы одна единица, так как по условию слагаемые не могут равняться нулю. Мы получили задачу про "честных" пиратов! Сундуками здесь являются единицы. Итак, нам нужно поставить две перегородки, а мест между десятью единицами для них ровно девять. Количество способов выбрать два места для перегородок из девяти мест равно $$\dfrac{9 \cdot 8}{2 \cdot 1} = 36.$$

Ответ: $36$.

Задачи

Игра в мини-гольф состоит в прохождении площадок, на каждой из которых нужно забить мяч в лунку. После того, как мяч оказывается в лунке, игрок переходит на следующую площадку. Число ударов на прохождение отдельной площадки не ограничено. Когда все площадки пройдены, в таблице отмечается общее число ударов, которое потребовалось игроку. Сколько существует различных способов пройти пять площадок за двенадцать ударов?

Решение.

Двенадцать ударов нам нужно распределить между пятью площадками. Для этого потребуется четыре перегородки. На каждой площадке должен быть сделан хотя бы один удар. Эта задача о "честных" пиратах. Сундуками здесь являются удары, а пиратами — площадки. Нам нужно поставить четыре перегородки, а мест для них ровно одиннадцать, между "сундуками". Количество способов выбрать четыре места из одинадцати равно $$\dfrac{11 \cdot 10 \cdot 9 \cdot 8}{4 \cdot 3 \cdot 2 \cdot 1} = 330.$$

Ответ: $330$.

Решение
Ответ

В кафе продаются пирожные четырёх видов: эклеры, песочные, бисквитные и слоёные. Сколькими способами можно составить набор из шести пирожных?

Решение.

Шесть пироженых нужно распределить между четырьмя видами. Для этого потребуется три перегородки. Какой-то вид мы можем вообще не выбрать. Видим задачу о "нечестных" пиратах. Сундуками здесь являются пироженые, а пиратами — разновидности пироженых. Зарезервируем $6 + 3 = 9$ мест под "сундуки" и перегородки. Из этих девяти мест нужно выбрать три для перегородок. Количество способов это сделать равно $$\dfrac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84.$$

Ответ: $84$.

Решение
Ответ

Шесть ящиков занумерованы числами от $1$ до $6$. Сколькими способами можно разложить по этим ящикам десять одинаковых шаров так, чтобы ни один ящик не оказался пустым?

Решение.

Десять шаров нам нужно распределить между шестью ящиками. Для этого потребуется пять перегородок. Перегородки можно ставить только между шарами, так как в каждом ящике должен оказаться хотя бы один шар. Следовательно, мы имеем всего девять мест для перегородок. Количество способов выбрать четыре места для шаров (перегородки поставим на оставшиеся места) из девяти доступных равно $$\dfrac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126.$$

Ответ: $126$.

Решение
Ответ

Сколько решений имеет уравнение $$x_1 + x_2 + x_3 + x_4 + x_5 = 6$$ в целых неотрицательных числах?

Решение.

Число шесть представим в виде шести единиц, которые нам нужно распределить между пятью слагаемыми. Для этого потребуется четыре перегородки. Слагаемые могут быть равны нулю, следовательно, ограничений у нас никаких нет. Зарезервируем $6 + 4 = 10$ мест под единицы и перегородки. Количество способов выбрать четыре места для перегородок из десяти доступных равно $$\dfrac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210.$$

Ответ: $210$.

Решение
Ответ

Сколько существует способов разложить три неразличимых шара в пять занумерованных ящиков?

Решение.

Нам нужно распределить три шара между пятью ящиками. Для этого потребуется четыре перегородки. Зарезервируем $3 + 4 = 7$ мест под шары и перегородки. Количество способов выбрать три места для шаров (перегородки поставим на оставшиеся места) из семи доступных равно $$\dfrac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35.$$

Ответ: $35$.

Решение
Ответ

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

Решение.

Нам нужно распределить пять галочек между тремя номерами шаров. Для этого потребуется две перегородки. Зарезервируем $5 + 2 = 7$ мест под галочки и перегородки. Количество способов выбрать два места для перегородок из семи доступных равно $$\dfrac{7 \cdot 6}{2 \cdot 1} = 21.$$

Ответ: $21$.

Решение
Ответ

Сколько решений имеет уравнение $$x + y + z + t = 20$$ в четных натуральных числах?

Решение.

Будем искать четные решения, то есть решения вида $x = 2 \tilde x$, $y = 2 \tilde y$, $z = 2 \tilde z$, $t = 2 \tilde t$. Подставим эти выражения в исходное уравнение и разделим его на два, получим $$\tilde x + \tilde y + \tilde z + \tilde t = 10,$$ где переменные принимают произвольные натуральные значения. Представим число $10$ в виде десяти единиц, которые нам необходимо распределить на четыре группы. Для этого потребуется три перегородки. В каждой группе должна присутствовать хотя бы одна единица, так как мы ищем только натуральные решения. Следовательно, мест для перегородок у нас ровно девять. Количество способов выбрать три места для перегородок из девяти доступных равно $$\dfrac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84.$$

Ответ: $84$.

Решение
Ответ

Сколько решений имеет уравнение $$x + y + z = 25$$ в нечетных натуральных числах?

Решение.

Будем искать нечетные решения, то есть решения вида $x = 2 \tilde x + 1$, $y = 2 \tilde y + 1$, $z = 2 \tilde z + 1$. Подставим эти выражения в исходное уравнение, приведем подобные слагаемые и разделим все уравнение на два, получим $$\tilde x + \tilde y + \tilde z = 11,$$ где переменные принимают целые неотрицательные целые значения. Представим число $11$ в виде одиннадцати единиц, которые нам необходимо распределить на три группы. Для этого потребуется две перегородки. Зарезервируем $11 + 2 = 13$ мест под единицы и перегородки. Количество способов выбрать два места для перегородок из тринадцати доступных равно $$\dfrac{13 \cdot 12}{2 \cdot 1} = 78.$$

Ответ: $78$.

Решение
Ответ

Сколько различных неупорядоченных наборов из трех цифр можно составить, используя цифры $1$, $2$, $3$, $4$, $5$, если цифры могут повторяться?

Решение.

Проведем аналогию с задачей про пиратов. Пусть пиратами будут пять доступных цифр, а сундуками — три позиции, на которые эти числа нужно расставить. Например, выбор числа $999$ в пиратских терминах будет обозначать, что мы отдали все три сундука девятому пирату. Итак, нам нужно распределить три сундука между пятью пиратами. Для этого потребуется четыре перегородки. Зарезервируем $3 + 4 = 7$ мест под сундуки и перегородки. Количество способов выбрать три места для сундуков (перегородки поставим на оставшиеся места) из семи доступных равно $$\dfrac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35.$$

Ответ: $35$.

Решение
Ответ

Сколько существует трехзначных чисел, в которых цифры идут в порядке неубывания?

Решение.

Для составления чисел мы можем использовать цифры от $1$ до $9$. Цифру $0$ использовать нельзя, так как корректное число не может начинаться с нуля, а по условию ноль всегда должен будет стоять первым. Порядок выбора в данном случае не имеет значения, так как этот порядок уже задан: цифры идут в порядке неубывания. Проведем аналогию с задачей про пиратов. Пусть пиратами будут девять доступных цифр, а сундуками — три позиции, на которые эти числа нужно расставить. Например, выбор числа $999$ в пиратских терминах будет обозначать, что мы отдали все три сундука девятому пирату. Итак, нам нужно распределить три сундука между девятью пиратами. Для этого потребуется восемь перегородок. Зарезервируем $3 + 8 = 11$ мест под сундуки и перегородки. Количество способов выбрать три места для сундуков (перегородки поставим на оставшиеся места) из одиннадцати доступных равно $$\dfrac{11 \cdot 10 \cdot 9}{3 \cdot 2 \cdot 1} = 165.$$

Ответ: $165$.

Решение
Ответ