Комбинаторика

Решение.

Приведем дроби к общему знаменателю. Для этого домножим вторую дробь на $n$, а третью — на $n(n - 1)$, получим $$\dfrac{n + 1}{n!} + \dfrac{n(n - 2)}{n!} - \dfrac{n(n - 1)}{n!}.$$ Сложим дроби и раскроем скобки $$\dfrac{n + 1 + n^2 - 2n - n^2 + n}{n!}.$$ После приведения подобных слагаемых будем иметь $$\dfrac{1}{n!}.$$

Решение.

В нашем слове будет $3n$ букв. Если бы все буквы были различны, то количество различных слов оказалось бы равно $P_{3n}$. Однако, порядок $n$ букв "е" для нас не имеет значения. Следовательно, по правилу деления нужно разделить этот результат на количество перестановок из $n$ букв, то есть на $P_n$. Аналогичный вывод делаем для букв "р" и "ш". В итоге получаем, что количество искомых слов равно $$\dfrac{P_{3n}}{(P_n)^3} = \dfrac{(3n)!}{(n!)^3}.$$

Решение.

Сначала вычислим количество рассадок без учета циклического сдвига. За нашим столом всего $2n$ мест. Рассадим женщин на места через одно. Всего существует $P_n$ способов рассадить $n$ человек на $n$ мест. На оставшиеся $n$ мест нужно рассадить мужчин. Снова получаем $P_n$ способов. По правилу умножения общее количество рассадок без учета циклического сдвига равно $P_n \cdot P_n$.

Теперь подумаем, сколько рассадок отличаются только циклическим сдвигом людей, например, по часовой стрелке. После рассадки мы можем попросить людей сместиться на одно место влево. В этом случае мы получим ту же рассадку. Мы можем пересаживать людей циклично ровно $n$ раз, после чего снова вернемся в изначальную рассадку. Итак, нам нужно объединить в одну рассадку $n$ рассадок, которые отличаются только циклическим сдвигом. Следовательно, итоговое количество рассадок будет в $n$ раз меньше, чем количество рассадок без учета циклического сдвига, то есть $$\dfrac{P_n \cdot P_n}{n} = \dfrac{n! \ n!}{n} = n!\ (n - 1)!.$$

Решение.

Обозначим буквой $n$ требуемое число задач. По условию каждому ученику достанется индивидуальный набор, состоящий их пяти задач. При этом выбор этих пяти задач должен осуществляться из $n$ задач без учета порядка выбора. Количество таких наборов равно $C_n^5$. Нам нужно найти минимальное натуральное число $n$, чтобы было выполнено неравенство $$C_n^5 \geq 100.$$ Подбором находим, что $C_8^5 = 56$ и $C_9^5 = 126$. Следовательно, искомое число $n = 9$.

Решение.

Обозначим буквой $n$ требуемое число простых задач. По условию каждому ученику достанется индивидуальный набор, состоящий их трех простых задач. При этом выбор этих трех задач должен осуществляться из $n$ задач без учета порядка выбора. Количество таких наборов равно $C_n^3$. Нам нужно найти минимальное натуральное число $n$, чтобы было выполнено неравенство $$C_n^3 \geq 100.$$ Находим, что $C_9^3 = 84$ и $C_{10}^3 = 120$. Следовательно, количество простых задач должно быть не менее $10$.

Аналогично поступим со сложными задачами. Обозначим буквой $m$ требуемое число сложных задач. Нам нужно найти минимальное натуральное число $m$, чтобы было выполнено неравенство $$C_m^2 \geq 100.$$ Находим, что $C_{14}^2 = 91$ и $C_{15}^2 = 105$. Следовательно, количество сложных задач должно быть не менее $15$.

Получаем, что суммарное количество задач должно быть не меньше, чем $$10 + 15 = 25.$$

Решение.

Заметим, что двойка входит в это произведение ровно $99$ раз, а именно, один раз в каждый множитель, начиная с $2!$. Тройка входит в это произведение $98$ раз: один раз в каждый множитель, начиная с $3!$. Рассуждая аналогично, получаем, что наше произведение можно записать в виде $$2^{99} \cdot 3^{98} \cdot 4^{97} \cdot \ldots \cdot 100^1.$$ Видим, что все нечетные числа входят в это произведение четное число раз. Сгруппируем их: $$ \begin{equation} \begin{gathered} (3^{98} \cdot 5^{96} \cdot 7^{94} \cdot \ldots \cdot 99^2) \cdot \\ \cdot (2^{99} \cdot 4^{97} \cdot \ldots \cdot 100^1). \end{gathered} \end{equation} $$ Первая скобка образует точный квадрат, а именно $$(3^{49} \cdot 5^{48} \cdot 7^{47} \cdot \ldots \cdot 99^1)^2.$$ Поработаем со второй скобкой. Все четные числа входят в это произведение нечетное число раз. Вынесем за скобку каждое четное число по одному разу, и в скобке остануются только четные степени, которые образуют точный квадрат. Таким образом, произведение во второй скобке равно $$ \begin{equation} \begin{gathered} (2^{49} \cdot 4^{48} \cdot \ldots \cdot 98^1)^2 \cdot \\ \cdot (2 \cdot 4 \cdot 6 \cdot \ldots \cdot 100). \end{gathered} \end{equation} $$ Осталось выделить квадрат в произведении четных чисел от $2$ до $100$. Вынесем из каждого множителя двойку. Всего множителей пятьдесят, поэтому мы получим $$ \begin{equation} \begin{gathered} 2^{50} \cdot 1 \cdot 2 \cdot 3 \cdot \ldots \cdot 50 =\\ = 2^{50} \cdot 50! = (2^{25})^2 \cdot 50!. \end{gathered} \end{equation} $$ Запишем полученное равенство полностью. $$ \begin{equation} \begin{gathered} 1! \cdot 2! \cdot 3! \cdot \ldots \cdot 100! = \\ = (3^{49} \cdot 5^{48} \cdot 7^{47} \cdot \ldots \cdot 99^1)^2 \cdot \\ \cdot (2^{49} \cdot 4^{48} \cdot \ldots \cdot 98^1)^2 \cdot\\ \cdot (2^{25})^2 \cdot 50!. \end{gathered} \end{equation} $$ Следовательно, если в исходном произведении убрать множитель $50!$, тогда результат умножения станет точным квадратом.

Решение.

Число $(2^n)!$ представляет из себя произведение всех натуральных чисел от $1$ до $2^n$, то есть $$(2^n)! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot 2^n.$$ Сгруппируем все нечетные числа в скобке, а из всех четных чисел вынесем двойку. Четных чисел ровно половина, то есть $2^n : 2 = 2^{n - 1}$ штук. Следовательно, мы вынесем $2^{n - 1}$ двоек, то есть число $2^{2^{n - 1}}$. Получится $$ \begin{equation} \begin{gathered} (2^n)! = (1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2^n - 1)) \cdot \\ \cdot 2^{2^{n - 1}} \cdot (1 \cdot 2 \cdot 3 \cdot \ldots \cdot 2^{n - 1}). \end{gathered} \end{equation} $$ Используем факториал, чтобы сократить запись, будем иметь $$ \begin{equation} \begin{gathered} (2^n)! = (1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2^n - 1)) \cdot \\ \cdot 2^{2^{n - 1}} \cdot (2^{n - 1})!. \end{gathered} \end{equation} $$ Обозначим степень двойки в разложении на простые множители числа $(2^n)!$ как $F(n)$. Из формулы выше видим следуюшую зависимость $$F(n) = 2^{n - 1} + F(n - 1).$$ Последовательно выражая значение функции $F(n)$ для все меньших $n$, получаем \begin{equation} \begin{gathered} F(n) = 2^{n - 1} + 2^{n - 2} + 2^{n - 3} +\\ + \ldots + 2^1 + F(1). \end{gathered} \end{equation} Но $F(1)$ по определению равно степени двойки в выражении $(2^1)!$, то есть равно $1$. Откуда искомая зависимость выражается формулой $$F(n) = 1 + 2^1 + 2^2 + \ldots + 2^{n - 1}.$$ Это геометрическая прогрессия со знаменателем $2$. По формуле суммы геометрической прогрессии получаем, что $$F(n) = 2^n - 1.$$

Решение.

Выберем сначала набор из стальных деталей, это можно сделать $C_{n_1}^{k_1}$ способами. Теперь выберем набор из деревянных деталей, этом можно сделать $C_{n_2}^{k_2}$ способами. По правилу умножения количество способов выбрать упорядоченную пару деталей равно $$C_{n_1}^{k_1} \cdot C_{n_2}^{k_2}.$$ Теперь нужно учесть, что все $(k_1 + k_2)$ деталей из выбранного набора можно переставлять местами. Каждый набор деталей можно разложить $P_{k_1 + k_2}$ способами. Следовательно, количество искомых выборок равно $$P_{k_1 + k_2} \cdot C_{n_1}^{k_1} \cdot C_{n_2}^{k_2}.$$

Решение.

Первую команду можно выбрать $C_n^k$ способами. Вторую команду — $C_{nk - k}^k$ способами. Третью команду — $C_{nk - 2k}^k$ способами. Последняя команда определяется $C_{k}^k = 1$ способом. По правилу умножения получаем, что количество команд с учетом порядка их выбора равно $C_{nk - k}^k \cdot C_{nk - 2k}^k \cdot \ldots \cdot C_{k}^k$. Запишем эти множители в обратном порядке и получим $$C_{k}^{k} \cdot C_{2k}^k \cdot \ldots \cdot C_{nk}^k.$$ Теперь нужно учесть, что разбиение на команды не зависит от порядка выбора команд. Переставить $n$ команд местами можно ровно $P_n$ способами. По правилу деления получаем, что искомое количество разбиений равно $$\dfrac{C_{k}^{k} \cdot C_{2k}^k \cdot \ldots \cdot C_{nk}^k}{P_n}.$$ Подставим в этот результат выражение для чисел $C_n^k = \dfrac{n!}{k!\ (n - k)!}$ и $P_n = n!$. После сокращений получим компактное выражение $$\dfrac{(nk)!}{n!\ (k!)^n}.$$ Заметим, что этот результат можно интепретировать так: $$\dfrac{P_{nk}}{P_n \cdot (P_k)^n}.$$

Решение.

Разложим $10^k$ на простые множители, получим $$2^k \cdot 5^k.$$ Теперь нам нужно распределить $k$ двоек и $k$ пятерок между тремя множителями. Распределим сначала двойки. Для каждой двойки нам нужно выбрать один множитель из трех, при этом порядок выбора нам не важен, и возможны повторения. Следовательно, количество способов распеределить двойки равно $\bar{C}_3^k$. Для пятерок аналогично получаем $\bar{C}_3^k$. Выбор двоек и пятерок осуществляется независимо, значит, по правилу умножения получаем, что искомое количество способов равно $$(\bar{C}_3^k)^2 = \dfrac{(k + 2)^2(k + 1)^2}{4}.$$

Можно было бы решить эту задачу с помощью перегородок. Так, для распределения $k$ двоек между тремя множителями нам потребуется две перегородки. Зарезервируем $k + 2$ места под двойки и перегородки. Количество способов выбрать два места из $(k + 2)$ доступных равно $C_{k + 2}^2$. Для пятерок имеем ту же формулу. По правилу умножения получаем известный результат $$(C_{k+2}^2)^2 = \dfrac{(k + 2)^2 (k + 1)^2}{4}. $$

Решение.

Сначала найдем наименьшее допустимое количество замков. По условию у любой группы из $(k - 1)$ человек не должно хватать ключа хотя бы от одного замка. При этом у каждой такой группы этот замок уникальный. Докажем это от противного. Предположим, что у двух групп не хватает ключа от одного и того же замка. Но тогда и у любых $k$ человек, набранных из этих двух групп, не хватает ключа от этого замка, а это противоречит условию. Итак, каждой группе из $(k - 1)$ человек не хватает ключа от уникального замка. Следовательно, минимальное число замков равно количеству различных групп из $(k - 1)$ человек, то есть $C_n^{k - 1}$.

Теперь подумаем, сколько должно быть ключей и как их распределить. Каждой группе из $(k - 1)$ человек не хватает уникального ключа. Занумеруем членов комиссии от $1$ до $n$ и выпишем по возрастанию все возможные группы из $(k - 1)$ человек. Пусть первой группе не хватает первого ключа, второй группе — второго и так далее.

Подсчитаем количество групп, в которые входит каждый член комиссии. Это количество равно числу способов добрать к нему в группу $(k - 2)$ человек из оставшихся $(n - 1)$ человек. Таким образом, каждый человек входит в $C_{n - 1}^{k - 2}$ групп, то есть у него не должно быть в наличии $C_{n - 1}^{k - 2}$ уникальных ключей. А не входит он в оставшиеся $$C_n^{k - 1} - C_{n - 1}^{k - 2}$$ групп, и как раз столько ключей у него и должно быть. Так как всего у нас $n$ человек, значит, общее количество ключей равно $$n(C_n^{k - 1} - C_{n - 1}^{k - 2}).$$ Ранее мы поняли, что количество замков равно $C_{n}^{k - 1}$, а значит, количество экземпляров каждого ключа равно $$\dfrac{n(C_n^{k - 1} - C_{n - 1}^{k - 2})}{C_{n}^{k - 1}}.$$ Воспользуемся равенством $C_n^k = \dfrac{n!}{(n - k)!\ k!}$ и упростим полученное выражение. После сокращений получаем, что количество ключей от каждого замка равно $$(n - k + 1).$$ Заметим, что мы можем подсчитать количество ключей у каждого человека вторым способом. А именно, общее число ключей $C_{n}^{k - 1} \cdot (n - k + 1)$ разделить на $n$: $$\dfrac{C_{n}^{k - 1} \cdot (n - k + 1)}{n}.$$ После сокращений имеем $$\dfrac{(n - 1)!}{(k - 1)!\ (n - k)!} = C_{n - 1}^{k - 1}.$$ Приравняем полученное выражение к числу ключей у каждого человека, найденному ранее. Получим замечательное тождество $$C_n^{k - 1} - C_{n - 1}^{k - 2} = C_{n - 1}^{k - 1}.$$ Смысл этой формулы мы обсудим в следующей статье, а сейчас пришло время записать ответ к нашей задаче.