-
Перебор вариантов
Как кодировать комбинации
-
Правило умножения
Как считать комбинации без перебора
-
Правило деления
Как учесть беспорядок
-
Метод перегородок
Как вычислить число разбиений
-
Размещения и сочетания
Как систематизировать выборки
-
Треугольник Паскаля
Как вывести свойства числа сочетаний
-
Бином Ньютона
Как раскрывать скобочки
Комбинаторика
Как считать комбинации
Правило деления
Сколько различных пар можно выбрать из четырех человек, если не имеет значения, кого выбрали в пару первым, а кого — вторым? Правило умножения, рассмотренное в предыдущей статье, позволяет дать ответ только в том случае, если порядок выбора имеет зачение. Введем обозначения. Занумеруем людей цифрами от $1$ до $4$. Пару людей теперь можно записать в виде неупорядоченной пары из двух цифр. Слово "неупорядоченной" означает, что пары, составленные из одинакового набора цифр, отличающиеся только их порядком, например, $\{1,\ 2\}$ и $\{2,\ 1\}$, мы будем считать одинаковыми. Теперь перед нами следующая задача.
Сколько различных неупорядоченных пар можно составить, используя без повторений цифры $1$, $2$, $3$, $4$?
Решение
Проанализируем, как число упорядоченных пар связано с числом неупорядоченных. Для этого выпишем все упорядоченные пары по возрастанию, а после обведем одинаковым цветом те из них, которые составлены из одинакового набора цифр.
| $12$ | $13$ | $14$ |
| $21$ | $23$ | $24$ |
| $31$ | $32$ | $34$ |
| $41$ | $42$ | $43$ |
Получилось $12$ упорядоченных пар. Например, в красный цвет мы покрасили те пары, которые состоят из цифр $1$ и $2$. Получилось ровно две красные пары, так как существует всего $2 \cdot 1 = 2$ способа переставить две цифры местами. Найдем число использованных цветов. Для этого разделим общее число пар на количество пар одного цвета. У нас получится $\dfrac{12}{2} = 6$. А каждому цвету соответствует ровно одна неупорядоченная пара. Значит, количество неупорядоченных пар равно $6$.
Ответ: $6$.
Увеличим размер выборки, чтобы лучше понять закономерность. Будем выбирать три цифры из четырех.
Сколько различных неупорядоченных троек можно составить, используя без повторений цифры $1$, $2$, $3$, $4$?
Решение
Выпишем все упорядоченные тройки и обведем одинаковым цветом те из них, которые составлены из одинакового набора цифр.
| $123$ | $124$ | $132$ | $134$ |
| $142$ | $143$ | $213$ | $214$ |
| $231$ | $234$ | $241$ | $243$ |
| $312$ | $314$ | $321$ | $324$ |
| $341$ | $342$ | $412$ | $413$ |
| $421$ | $423$ | $431$ | $432$ |
Получилось $24$ упорядоченных тройки. Существует ровно $3 \cdot 2 \cdot 1 = 6$ способов переставить три цифры. Следовательно, в каждый цвет мы покрасим $6$ троек. Найдем количество использованных цветов. Для этого разделим общее число троек на количество троек одного цвета. У нас получится $\dfrac{24}{6} = 4$. Следовательно, количество неупорядоченных троек равно $4$.
Ответ: $4$.
Решим аналогичную задачу с помощью правила умножения, не выписывая все упорядоченные наборы
Сколько различных неупорядоченных троек можно составить, используя без повторений цифры $1$, $2$, $3$, $4$, $5$?
Решение
На первое место в упорядоченной тройке можно поставить любую из пяти цифр, на второе — любую из четырех оставшихся, на третье место останется три цифры. Получилось $5 \cdot 4 \cdot 3 = 60$ упорядоченных троек. Существует ровно $3 \cdot 2 \cdot 1 = 6$ способов переставить три цифры. Найдем количество неупорядоченных троек. Для этого разделим общее число троек на количество способов переставить три цифры (это количество троек одного цвета в предыдущем примере). Итак, количество неупорядоченных троек равно $$\dfrac{60}{6} = 10.$$
Ответ: $10$.
Набор может быть упорядочен только частично, рассмотрим этот случай.
Сколько различных троек можно составить, используя без повторений цифры $1$, $2$, $3$, $4$, если при этом порядок первых двух цифр в тройке не важен?
Решение
На первое место в упорядоченной тройке можно поставить любую из четырех цифр, на второе — любую из трех оставшихся, на третье место останется две цифры. Получилось $4 \cdot 3 \cdot 2 = 24$ упорядоченные тройки. Существует ровно $2 \cdot 1 = 2$ способа переставить первые две цифры в каждой из этих троек. Значит, все упорядоченные тройки объединяются в группы, по две тройки в каждой. Найдем число этих групп. Для этого разделим общее число троек на количество цифр в каждой группе. Итак, количество нужных троек равно $$\dfrac{24}{2} = 12.$$
Ответ: $12$.
Дадим опредедение, связанное с предыдущей задачей.
На основе разобранных примеров сформулируем правило деления для неупорядоченных наборов.
А также правило деления для частично упорядоченных наборов.
Посмотрим, как эти правила применяются.
В шахматном турнире принимали участие пятнадцать шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире?
Решение
Первого шахматиста можно выбрать $15$ способами, а второго — $14$ способами. Значит, число упорядоченных пар шахматистов равно $15 \cdot 14$. Но нам неважно, Вася сыграл с Петей или Петя с Васей, так как это была одна и та же партия. Следовательно, нас интересует число неупорядоченных пар. Переставить двух шахматистов можно двумя способами. По правилу деления находим число партий: $$\dfrac{15 \cdot 14}{2} = 105.$$
Ответ: $105$.
Теперь поиграем в слова.
Словом назовем любую комбинацию букв. Порядок букв имеет значение, то есть слова "аб" и "ба" будем считать различными. Сколько различных слов можно составить, переставляя буквы в слове "ананас"?
Решение
Пусть каждая буква в слове уникальна и имеет свой номер, а именно, "а1н1а2н2а3с1". Переставить такие занумерованные буквы можно $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ способами. Порядок трех букв "а" нам не важен: по правилу деления нужно будет $720$ разделить на количество способов переставить три буквы, $3\cdot 2\cdot 1 = 6$. Порядок двух букв "н" также неважен, поэтому $720$ разделим еще на $2\cdot 1 = 2$. Получим $$\dfrac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3\cdot 2\cdot 1 \cdot 2\cdot 1} = 60.$$
Ответ: $60$.
Рассмотрим более сложный пример.
Сколькими способами можно разбить двенадцать человек на две команды по шесть человек?
Решение
Выберем $6$ человек из $12$, они отправятся в первую команду. Число таких упорядоченных выборок равно $12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7$. Порядок, в котором мы выбирали этих шесть человек не важен, их можно переставить $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ способами. По правилу деления число неупорядоченных выборок составляет $$\dfrac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 924.$$ Но нас просят найти не количество способов выбрать $6$ человек из $12$, а число способов разбить на две команды. Поясним в чем разница. Так, если мы выбрали бы людей с номерами $\{1,\ 2,\ 3,\ 4,\ 5,\ 6\}$, то получили бы те же самые две команды, как если выбрали бы людей с оставшимися номерами: $\{7,\ 8,\ 9,\ 10,\ 11,\ 12\}$. То есть, порядок, в котором эти две команды выбраны, не важен. По правилу деления нужно наш результат еще раз разделить на число способов переставить две команды местами, а именно, на $2\cdot 1 = 2$. Итак, $$\dfrac{924}{2} = 462.$$
Ответ: $462$.
Задачи
Таня ведет дневник погоды, каждый день отмечая, солнце сегодня или дождь. Согласно прогнозу, на следующей неделе будет пять солнечных дней и два дождливых. Сколько различных записей может появиться у Тани в дневнике?
Решение.
Нам нужно подсчитать количество способов выбрать два дня из семи, когда будет дождь. Первый дождливый день можно выбрать семью способами, а второй — шестью. По правилу умножения количество упорядоченных пар из двух дней равно $7 \cdot 6$. Но нам нужно учесть, что порядок выбора не важен, то есть не важно, отметила ли Таня сначала дождь во вторник, а потом — в четверг, или наоборот. Обе ситуации приведут нас к одной и той же записи в дневнике. По правилу деления получаем, что искомое количество записей равно $$\dfrac{7 \cdot 6}{2 \cdot 1} = 21.$$
Ответ: $21$.
В шахматном турнире каждый из участников сыграл только одну партию с каждым из остальных, причем всего было сыграно $136$ партий. Сколько всего было шахматистов?
Решение.
Обозначим буквой $n$ количество шахматистов. Чтобы найти число партий, нужно подсчитать, сколько различных пар шахматистов можно составить. Первого игрока в пару можно выбрать $n$ способами, а второго $(n - 1)$ способом. По правилу умножения количество упорядоченных пар шахматистов равно $n(n - 1)$. А число партий в два раза меньше, так как пара "Петя - Вася" и пара "Вася - Петя" представляют одну и ту же партию. По правилу деления получаем, что общее число партий равно $$\dfrac{n(n - 1)}{2 \cdot 1} = 136.$$ Решив это уравнение, получаем $n = 17$.
Ответ: $17$.
На прямой отметили пять точек. Сколько получилось отрезков?
Решение.
Отрезок однозначно определяется двумя точками. Началом отрезка может служить любая из пяти доступных точек, концом отрезка — любая из четырех оставшихся точек. По правилу умножения количество упорядоченных пар точек равно $5 \cdot 4$. Порядок выбора этих двух точек не важен. По правилу деления получаем, что количество отрезков равно $$\dfrac{5 \cdot 4}{2 \cdot 1} = 10.$$
Ответ: $10$.
Сколько диагоналей у двенадцатиугольника?
Решение.
Диагональ однозначно определяется двумя вершинами без учета их порядка. Первую вершину можно выбрать двенадцатью способами. На место второй вершины претендуют все вершины, кроме выбранной и двух вершин рядом с ней, так как они являются концами сторон, а не диагоналей. Итак, вторую вершину можно выбрать $12 - 3 = 9$ способами. Следовательно, количество диагоналей равно $$\dfrac{12 \cdot 9}{2 \cdot 1} = 54.$$
Ответ: $54$.
На первой из двух параллельных прямых лежит пять точек, на второй — четыре. Сколько существует треугольников с вершинами в этих точках?
Решение.
Рассмотрим случай, когда две вершины треугольника лежат на первой прямой. Количество способов выбрать две точке из пяти без учета порядка равно $\dfrac{5 \cdot 4}{2 \cdot 1} = 10$. Третью вершину треугольника на второй прямой можно выбрать четырьмя способами. Значит, количество таких треугольников равно $$10 \cdot 4 = 40.$$ Теперь рассмотрим случай, когда две вершины треугольника лежат на второй прямой. Количество способов выбрать две точке из четырех без учета порядка равно $\dfrac{4 \cdot 3}{2 \cdot 1} = 6$. Третью вершину треугольника на первой прямой можно выбрать пятью способами. Значит, количество таких треугольников равно $$6 \cdot 5 = 30.$$ Получаем, что итоговое количество треугольников составляет $$40 + 30 = 70.$$
Ответ: $70$.
Сколько существует шестизначных чисел, у которых сумма цифр равна трем?
Решение.
Рассмотрим случай, когда наше число состоит из тройки и пяти нулей. Тогда получим единственный вариант — число $300\ 000$.
Теперь рассмотрим случай, когда число состоит из двойки, единицы и четырех нулей. Единицу можно поставить на первое место, а двойку на любое из пяти оставшихся мест (пять способов). Можно также поменять двойку и единицу местами (еще пять способов). Получаем десять вариантов.
Наконец, рассмотрим случай, когда число состоит из трех единиц и трех нулей. Первую единицу нужно поставить вперед, так как корректное число не может начинаться с нуля. Вторую единицу можно поставить на любое из пяти оставшихся мест, третью единицу — на любое из четырех свободных мест. Заметим, что нам не важен порядок расстановки двух последних единиц. Следовательно, количество шестизначных чисел из трех нулей и трех единиц равно $$\dfrac{5 \cdot 4}{2} = 10.$$ Получаем, что количество шестизначных чисел, у которых сумма цифр равна трем, равно $$1 + 10 + 10 = 21.$$
Ответ: $21$.
На плоскости отмечено десять точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?
Решение.
Треугольник однозначно определяется тремя точками независимо от их порядка. Количество способов выбрать три точки из десяти без учета порядка выбора равно $$\dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120.$$
Ответ: $120$.
Сколькими способами можно разложить в ряд четыре красных и шесть синих шаров?
Решение.
Зарезервируем $4 + 6 = 10$ мест под наши шары и выберем из них четыре места под красные шары. Количество способов выбрать четыре места из десяти без учета порядка выбора равно $$\dfrac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210.$$
Ответ: $210$.
Сколькими способами можно переставить буквы слова "Юпитер" так, чтобы и гласные, и согласные шли в алфавитном порядке?
Решение.
Зарезервируем шесть мест под буквы нашего слова. Выберем три места для гласных букв. Порядок выбора не имеет значения, так как на самом левом месте в этом случае будет стоять буква "е", далее буква "и", потом — "ю". Количество способов выбрать три места из шести без учета порядка выбора равно $$\dfrac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20.$$ На оставшиеся места распределим согласные буквы, их порядок определен единственным образом.
Ответ: $20$.
Труппа театра состоит из десяти артистов. Сколькими способами можно выбрать из неё в течение двух вечеров по три человека для участия в спектаклях так, чтобы ни один артист не участвовал в двух спектаклях?
Решение.
На первый вечер нам нужно выбрать трех артистов из десяти. Количество способов выбрать трех человек из десяти учета порядка выбора равно $$\dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120.$$ На второй вечер нам нужно выбрать трех артистов уже из семи, так как трех людей, которые работали в первый вечер, выбирать по условию нельзя. Количество способов выбрать трех человек из семи без учета порядка выбора равно $$\dfrac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35.$$ По правилу умножения получаем, что искомое число способов равно $$120 \cdot 35 = 4200.$$
Ответ: $4200$.
Сколькими способами можно разбить девять человек на три команды по три человека?
Решение.
Сначала из девяти человек выберем трех человек в первую команду. Так как порядок выбора не важен, то количество способов это сделать равно $$\dfrac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84.$$ Теперь выберем трех человек из шести оставшихся, они пойдут во вторую команду. Количество способов это сделать равно $$\dfrac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20.$$ Оставшиеся три человека составляют третью команду единственным образом. Теперь нужно учесть, что порядок, в котором были определены эти три команды, не имеет значения. Следовательно, по правилу деления общее количество способов разбить девять человек на три команды равно $$\dfrac{84 \cdot 20 \cdot 1}{3 \cdot 2 \cdot 1} = 280.$$
Ответ: $280$.
Сколькими способами можно разбить восемь человек на пары?
Решение.
Сначала из восьми человек выберем двух человек в первую пару. Так как порядок выбора не важен, то число способов это сделать равно $$\dfrac{8 \cdot 7}{2 \cdot 1} = 28.$$ Теперь выберем вторую пару из шести оставшихся людей. Количество способов это сделать равно $$\dfrac{6 \cdot 5}{2 \cdot 1} = 15.$$ Третью пару будем выбирать уже из четырех человек: $$\dfrac{4 \cdot 3}{2 \cdot 1} = 6.$$ Оставшиеся два человека однозначно определяют четвертую пару. Теперь нужно учесть, что порядок, в котором были определены эти четыре пары, не имеет значения. Следовательно, по правилу деления общее число способов разбить восемь человек на четыре пары равно $$\dfrac{28 \cdot 15 \cdot 6 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 105.$$
Ответ: $105$.
Имеется десять белых и семь чёрных шаров. Сколькими способами можно все шары разложить в ряд так, чтобы никакие два чёрных шара не лежали рядом?
Решение.
Разложим сначала десять белых шаров. Черные шары можно положить в промежутки между белыми и еще на два места по краям, всего $11$ мест, которые отмечены зеленым на рисунке.
Из этих мест нам нужно выбрать семь для черных шаров. Порядок раскладки черных шаров не имеет значения. По правилу деления получаем, что количество нужных раскладок равно $$\dfrac{11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 330.$$
Ответ: $330$.
На плоскости отмечено шесть точек так, что никакие три из них не лежат на одной прямой. Какое наибольшее число выпуклых четырехугольников может быть с вершинами в этих точках?
Решение.
Оценим максимально возможное число произвольных четырехугольников. Любой четырехугольник однозначно определяется четырьмя точками. Количество способов выбрать четыре точки из данных шести без учета порядка выбора равно $$\dfrac{6 \cdot 5 \cdot 4 \cdot 3}{4 \cdot 3 \cdot 2 \cdot 1} = 15.$$ Теперь нужно привести такой пример расположения шести точек на плоскости, что любая четверка точек является вершинами выпуклого четырехугольника. Напомним, что по определению выпуклым называется четырехугольник, в котором все внутренние углы меньше $180^\circ$. Например, можно расположить наши точки равномерно вдоль окружности.
Ответ: $15$.
В шахматном кружке занимаются две девочки и семь мальчиков. Для участия в соревновании необходимо составить команду из четырёх человек, в которую обязательно должна входить хотя бы одна девочка. Сколькими способами это можно сделать?
Решение.
Сначала найдем количество команд из четырех человек без ограничений на участие девочек. Для этого нужно найти число способов выбрать четыре человека из девяти без учета порядка выбора. По правилу деления получаем $$\dfrac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126.$$ Теперь найдем количество команд, которые состоят только из мальчиков. Для этого нужно найти число способов выбрать четыре человека из семи мальчиков без учета порядка выбора. Снова по правилу деления получаем $$\dfrac{7 \cdot 6 \cdot 5 \cdot 4}{4 \cdot 3 \cdot 2 \cdot 1} = 35.$$ Значит, количество команд, в которых есть хотя бы одна девочка, равно $$126 - 35 = 91.$$
Ответ: $91$.
В классе, в котором учатся Петя и Ваня, десять человек. Сколькими способами можно выбрать из этого класса команду из четырех человек так, чтобы Петя и Ваня не входили в команду одновременно?
Решение.
Сначала найдем количество команд из четырех человек без ограничений на участие Пети и Вани. Для этого нужно найти число способов выбрать четыре человека из десяти без учета порядка выбора. По правилу деления получаем $$\dfrac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210.$$ Теперь найдем количество команд, в которые Петя и Ваня входят одновременно. Для этого нужно найти число способов добрать два человека к Пете и Ване в команду из восьми оставшихся учеников. Снова по правилу деления получаем $$\dfrac{8 \cdot 7}{2 \cdot 1} = 28.$$ Значит, количество команд, в которые Ваня и Петя не входят одновременно, равно $$210 - 28 = 182.$$
Ответ: $182$.
Сколько существует пятизначных чисел, в которых цифры идут в порядке убывания?
Решение.
Наше число будет записано с помощью пяти различных цифр, порядок которых заранее определен. Эти пять цифр можно выбрать из любых десяти цифр (от нуля до девяти). Количество способов выбрать пять цифр из десяти без учета порядка выбора равно $$\dfrac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 252.$$
Ответ: $252$.
Сколько существует пятизначных чисел, в которых цифры идут в порядке возрастания?
Решение.
Наше число будет записано с помощью пяти различных цифр, порядок которых заранее определен. Эти пять цифр можно выбрать из любых девяти цифр, кроме нуля, так как число не может начинаться с нуля, а в записи по возрастанию ноль будет всегда стоять первым. Количество способов выбрать пять цифр из девяти без учета порядка выбора равно $$\dfrac{9 \cdot 8 \cdot 7 \cdot 6 \cdot 5}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 126.$$
Ответ: $126$.
На библиотечной полке стоят двенадцать одинаковых книг. Сколькими способами можно взять из них пять, никакие две из которых не стоят рядом?
Решение.
Переформулируем задачу. Поставим на пять книг, которые мы собираемся взять, отметки и вычислим количество способов расставить все книги так, чтобы никакие две книги с отметками не стояли рядом. Расположим сначала семь книг без отметок. Теперь для книг с отметками сформировалось восемь доступных мест: шесть мест между книгами без отметок и два места по краям. Количество способов выбрать пять мест для книг с отметками из восьми доступных равно $$\dfrac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4}{5 \cdot 4 \cdot 3 \cdot 3 \cdot 2 \cdot 1} = 56.$$
Ответ: $56$.
Туристов восемь человек. Они рассаживаются в две машины: в одной может поместиться четыре человека, а в другой — шесть. Сколькими способами они могут распределиться в эти машины?
Решение.
Сначала рассмотрим случай, когда в большую машину сядет шесть человек, а в маленькую — два. Количество способов выбрать двух человек из восьми равно $$\dfrac{8 \cdot 7}{2 \cdot 1} = 28.$$ Теперь рассмотрим случай, когда в большую машину сядет пять человек, а в маленькую — три. Количество способов выбрать трех человек из восьми равно $$\dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56.$$ Наконец, рассмотрим случай, когда в обе машины сядет по четыре человека. Количество способов выбрать четырех человек из восьми равно $$\dfrac{8 \cdot 7 \cdot 6 \cdot 4}{4 \cdot 3 \cdot 2 \cdot 1} = 70.$$ Таким образом, общее количество требуемых рассадок равно $$28 + 56 + 70 = 154.$$
Ответ: $154$.
Тест по английскому языку сдавали десять школьников. Известно, что любые пять школьников ответили вместе на все вопросы, а любые четыре школьника ответили вместе не на все вопросы. При каком наименьшем количестве вопросов теста такое могло случиться?
Решение.
По условию для каждой группы из четырех школьников найдется хотя бы один вопрос, на который никто из этой группы не ответил. При этом у каждой такой группы этот вопрос уникальный. Докажем это от противного. Предположим, что у двух групп нет ответа на один и тот же вопрос. Но тогда и у любых пяти школьников, набранных из этих двух групп, нет ответа на этот вопрос, а это противоречит условию. Итак, у каждой группы из четырех школьников есть уникальный вопрос, на который у них нет ответа. Следовательно, минимальное количество вопросов в тесте равно количеству различных групп из четырех школьников. По правилу деления находим $$\dfrac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210.$$
Ответ: $210$.
Четыре пирата сложили награбленное в сундук. Сколько замков должен иметь сундук, сколько ключей для них нужно изготовить и как их разделить между всеми пиратами, чтобы доступ к сокровищам был возможен тогда и только тогда, когда соберутся не менее трех пиратов?
Решение.
Сначала найдем наименьшее допустимое количество замков. По условию у любой пары пиратов не должно хватать ключа хотя бы от одного замка. При этом у каждой пары этот замок уникальный. Докажем это от противного. Предположим, что у двух пар не хватает ключа от одного и того же замка. Но тогда и у любых трех пиратов, набранных из этих двух пар, не хватает ключа от этого замка, а это противоречит условию. Итак, каждой паре пиратов не хватает ключа от уникального замка. Следовательно, минимальное число замков равно количеству различных пар пиратов, то есть $$\dfrac{4 \cdot 3}{2 \cdot 1} = 6.$$
Теперь найдем минимальное количество ключей. Попробуем найти симметричное решение задачи: чтобы от каждого замка было одинаковое число ключей и каждому пирату также досталось одинаковое число ключей. Чтобы это было возможно, количество ключей должно делиться на шесть (число замков) и на четыре (число пиратов). Минимальное такое число это $12$. Следовательно, должно быть по $12 : 6 = 2$ ключа от каждого замка.
Остался вопрос о том, как распределить ключи между пиратами. Каждому достанется по $12 : 4 = 3$ ключа. При этом каждой паре пиратов должно не хватать уникального ключа. Занумеруем пиратов от $1$ до $4$ и выпишем по возрастанию все возможные пары пиратов. Пусть первой паре не хватает первого ключа, второй паре — второго и так далее.
| Пара пиратов | Отсутствующий ключ |
|---|---|
| 12 | 1 |
| 13 | 2 |
| 14 | 3 |
| 23 | 4 |
| 24 | 5 |
| 34 | 6 |
Первый пират входит в пары $12$, $13$ и $14$. У этих пар нет ключей с номерами $1$, $2$ и $3$. Следовательно, у первого пирата должны быть все остальные ключи: $456$. Аналогично определим наборы ключей у других пиратов и занесем их номера в таблицу.
| Пират | Ключи |
|---|---|
| 1 | 456 |
| 2 | 236 |
| 3 | 135 |
| 4 | 124 |
Ответ: $6$ замков, по $2$ ключа от каждого. Первому пирату отдать ключи от замков с номерами $456$, второму — $236$, третьему — $135$, четвертому — $124$.