Страница 230 - гдз по алгебре 9 класс учебник Никольский, Потапов

763. Доказываем. Докажите формулу: $A_n^k = \frac{n!}{(n-k)!}$.

Доказываем. Числом размещений из $n$ элементов по $k$, которое обозначается $A_n^k$, называется количество способов составить упорядоченные наборы (кортежи) длины $k$ из множества, содержащего $n$ различных элементов. Докажем формулу для вычисления этого числа, исходя из его комбинаторного смысла.

Будем формировать упорядоченный набор (размещение) последовательно, выбирая по одному элементу на каждую позицию от 1-й до $k$-й.
Для выбора первого элемента набора есть $n$ способов, так как можно взять любой из $n$ элементов исходного множества.
После того как первый элемент выбран, для выбора второго элемента остается $n-1$ способ, так как один элемент уже занят и не может быть выбран повторно.
Аналогично, для выбора третьего элемента остается $n-2$ способа.
Продолжая эту логику, для выбора последнего, $k$-го элемента, у нас останется $n - (k-1) = n - k + 1$ способов.

По правилу умножения в комбинаторике, общее число способов составить такой упорядоченный набор равно произведению числа способов выбора для каждой позиции:
$A_n^k = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)$

Теперь преобразуем полученное выражение к виду с факториалами. Напомним, что факториал числа $m$ ($m!$) — это произведение всех натуральных чисел от 1 до $m$.
Умножим и разделим наше выражение на $(n-k)! = (n-k) \cdot (n-k-1) \cdot \ldots \cdot 2 \cdot 1$. Это не изменит значения выражения.
$A_n^k = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1) \cdot (n-k)!}{(n-k)!}$

В числителе дроби теперь находится произведение всех натуральных чисел от $n$ до 1, что по определению равно $n!$.
$n \cdot (n-1) \cdot \ldots \cdot (n-k+1) \cdot (n-k) \cdot \ldots \cdot 1 = n!$
Знаменатель остался равен $(n-k)!$.

Таким образом, мы приходим к искомой формуле:
$A_n^k = \frac{n!}{(n-k)!}$
Что и требовалось доказать.

Ответ: Формула доказана.

764. a) Сколькими различными способами можно распределить между шестью лицами две разные путёвки?

б) Сколькими способами можно присудить трём лицам из шести три разные премии?

а) В данной задаче требуется найти число способов распределить 2 разные путёвки среди 6 человек. Поскольку путёвки разные, важен не только факт получения путёвки, но и то, какая именно путёвка достанется человеку. Это означает, что порядок важен. Также, по смыслу задачи, один человек не может получить обе путёвки. Следовательно, мы имеем дело с размещениями без повторений.

Рассуждать можно следующим образом:

1. Первую путёвку можно отдать любому из 6 человек. Существует 6 вариантов.

2. После того как первая путёвка отдана, остаётся 5 человек, которые могут получить вторую путёвку. Существует 5 вариантов.

Согласно правилу умножения в комбинаторике, общее число способов равно произведению числа вариантов для каждого шага:

$N = 6 \times 5 = 30$

Это же решение можно получить с помощью формулы для числа размещений из $n$ элементов по $k$:

$A_n^k = \frac{n!}{(n-k)!}$

В нашем случае, $n=6$ (общее количество людей) и $k=2$ (количество путёвок). Подставляем значения в формулу:

$A_6^2 = \frac{6!}{(6-2)!} = \frac{6!}{4!} = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{4 \times 3 \times 2 \times 1} = 6 \times 5 = 30$

Ответ: 30.

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

Рассуждаем по шагам:

1. Первую премию можно присудить любому из 6 человек (6 вариантов).

2. Вторую премию можно присудить любому из оставшихся 5 человек (5 вариантов).

3. Третью премию можно присудить любому из оставшихся 4 человек (4 варианта).

Общее число способов по правилу умножения:

$N = 6 \times 5 \times 4 = 120$

Используем формулу для числа размещений из $n$ по $k$, где $n=6$ и $k=3$:

$A_6^3 = \frac{6!}{(6-3)!} = \frac{6!}{3!} = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1} = 6 \times 5 \times 4 = 120$

Ответ: 120.

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

Данная задача относится к разделу комбинаторики, а именно к задачам на размещения без повторений. Нам необходимо найти количество способов, которыми можно выбрать 3-х человек из 7 и расставить их по трем призовым местам. Поскольку призовые места (первое, второе и третье) различны, порядок, в котором выбираются шахматисты, имеет значение.

Для решения можно применить комбинаторное правило умножения. Рассуждаем последовательно:

1. На первое место может претендовать любой из 7 шахматистов. Следовательно, есть 7 вариантов.

2. После того как первое место занято одним шахматистом, на второе место могут претендовать оставшиеся 6 человек. Таким образом, есть 6 вариантов.

3. Соответственно, на третье место остается 5 претендентов.

Чтобы найти общее число способов распределения мест, нужно перемножить количество вариантов для каждого места: $7 \times 6 \times 5 = 210$.

Также для решения этой задачи можно использовать формулу для числа размещений из $n$ элементов по $k$: $A_n^k = \frac{n!}{(n-k)!}$ где $n$ — общее число элементов (в нашем случае $n=7$ шахматистов), а $k$ — количество выбираемых элементов (в нашем случае $k=3$ призовых места).

Подставляя значения в формулу, получаем: $A_7^3 = \frac{7!}{(7-3)!} = \frac{7!}{4!} = \frac{7 \times 6 \times 5 \times 4!}{4!} = 7 \times 6 \times 5 = 210$.

Оба метода дают одинаковый результат. Существует 210 способов распределить три первых места между семью шахматистами.

Ответ: 210

766. У билетного кассира имеются для продажи билеты на автобус с номерами от 000000 до 999999. Сколько номеров билетов из этого набора записаны разными цифрами?

По условию задачи, номера билетов являются шестизначными числами в диапазоне от 000000 до 999999. Это означает, что номер билета представляет собой последовательность из 6 цифр, и на любой позиции, включая первую, может стоять ноль.

Нам необходимо найти количество таких номеров, у которых все шесть цифр различны. Для составления номеров мы можем использовать 10 цифр: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Задача сводится к нахождению числа размещений без повторений из 10 элементов по 6. Будем определять количество вариантов для каждой из шести позиций в номере билета последовательно.

• На первую позицию можно поставить любую из 10 цифр. Количество вариантов: 10.
• На вторую позицию можно поставить любую из оставшихся 9 цифр (так как одна цифра уже использована на первой позиции). Количество вариантов: 9.
• На третью позицию можно поставить любую из оставшихся 8 цифр. Количество вариантов: 8.
• На четвертую позицию можно поставить любую из оставшихся 7 цифр. Количество вариантов: 7.
• На пятую позицию можно поставить любую из оставшихся 6 цифр. Количество вариантов: 6.
• На шестую позицию можно поставить любую из оставшихся 5 цифр. Количество вариантов: 5.

Согласно комбинаторному правилу произведения, общее число способов составить такой номер равно произведению числа вариантов для каждой позиции:

$N = 10 \times 9 \times 8 \times 7 \times 6 \times 5$

Это число также можно вычислить с помощью формулы для числа размещений без повторений из $n$ элементов по $k$:

$A_n^k = \frac{n!}{(n-k)!}$

В нашем случае $n = 10$ (количество цифр) и $k = 6$ (длина номера билета):

$A_{10}^6 = \frac{10!}{(10-6)!} = \frac{10!}{4!} = 10 \times 9 \times 8 \times 7 \times 6 \times 5 = 151200$

Таким образом, существует 151 200 номеров билетов, которые записаны шестью различными цифрами.

Ответ: 151200

767. У билетного кассира имеются для продажи билеты на автобус с номерами от 000000 до 999999. Сколько номеров билетов из этого набора записаны без нулей?

Номера билетов на автобус находятся в диапазоне от 000000 до 999999. Это означает, что каждый номер является шестизначным числом, где на каждой из шести позиций может стоять любая цифра от 0 до 9.

Нам необходимо найти количество номеров, в записи которых не встречается цифра 0. Это значит, что для каждой из шести позиций в номере можно использовать только цифры из множества {1, 2, 3, 4, 5, 6, 7, 8, 9}. В этом множестве 9 цифр.

Рассмотрим каждую позицию в шестизначном номере:

• На первой позиции может стоять любая из 9 цифр (от 1 до 9).
• На второй позиции также может стоять любая из 9 цифр.
• Аналогично для третьей, четвертой, пятой и шестой позиций — по 9 вариантов для каждой.

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

Общее количество номеров, записанных без нулей, вычисляется по формуле:
$N = 9 \times 9 \times 9 \times 9 \times 9 \times 9 = 9^6$

Вычислим значение этого выражения:
$9^6 = 531441$

Таким образом, существует 531 441 номер билета, в записи которого не используется цифра 0.

Ответ: 531441

768. У кассира автобуса имеются для продажи билеты на автобус с номерами от 000000 до 999999. Счастливым назовём билет, у которого сумма первых трёх цифр совпадает с суммой последних трёх цифр.

а) Сколько существует счастливых билетов, у которых сумма всех цифр равна 0; 2; 4; 6; 8?

б) Сколько всего счастливых билетов у кассира?

Номер автобусного билета представляет собой шестизначное число от 000000 до 999999. Обозначим его как $d_1d_2d_3d_4d_5d_6$.

Согласно условию, билет называется счастливым, если сумма первых трёх цифр равна сумме последних трёх цифр: $d_1+d_2+d_3 = d_4+d_5+d_6$.

Пусть $k$ – это общая сумма для каждой тройки цифр, т.е. $k = d_1+d_2+d_3 = d_4+d_5+d_6$. Обозначим через $N(k)$ количество способов представить число $k$ в виде суммы трёх цифр (каждая цифра от 0 до 9).

Тогда для определённого значения суммы $k$, количество счастливых билетов будет равно $(N(k))^2$, так как существует $N(k)$ вариантов для первой тройки цифр и $N(k)$ независимых вариантов для второй тройки.

а) Сколько существует счастливых билетов, у которых сумма всех цифр равна 0; 2; 4; 6; 8?

Сумма всех шести цифр $S$ для счастливого билета равна $S = (d_1+d_2+d_3) + (d_4+d_5+d_6) = k + k = 2k$. Следовательно, сумма всех цифр счастливого билета всегда является чётным числом. Значение суммы для каждой тройки цифр равно $k = S/2$.

Найдём количество счастливых билетов для каждого из заданных значений $S$.

• Сумма всех цифр равна 0:

  $S=0$, значит $k = 0/2 = 0$. Нам нужно найти количество способов $N(0)$ получить сумму 0 из трёх цифр. Единственный способ – это 0+0+0=0. Таким образом, $N(0) = 1$. Количество счастливых билетов: $(N(0))^2 = 1^2 = 1$. Это билет 000000.

• Сумма всех цифр равна 2:

  $S=2$, значит $k = 2/2 = 1$. Найдём $N(1)$. Сумму 1 можно получить комбинациями цифр (1, 0, 0). Существует 3 перестановки этих цифр: 100, 010, 001. Таким образом, $N(1) = 3$. Количество счастливых билетов: $(N(1))^2 = 3^2 = 9$.

• Сумма всех цифр равна 4:

  $S=4$, значит $k = 4/2 = 2$. Найдём $N(2)$. Сумму 2 можно получить комбинациями (2, 0, 0) (3 перестановки) и (1, 1, 0) (3 перестановки). Всего $N(2) = 3+3 = 6$. Количество счастливых билетов: $(N(2))^2 = 6^2 = 36$.

• Сумма всех цифр равна 6:

  $S=6$, значит $k = 6/2 = 3$. Найдём $N(3)$. Сумму 3 можно получить комбинациями (3, 0, 0) (3 перестановки), (2, 1, 0) ( $3! = 6$ перестановок) и (1, 1, 1) (1 перестановка). Всего $N(3) = 3+6+1 = 10$. Количество счастливых билетов: $(N(3))^2 = 10^2 = 100$.

• Сумма всех цифр равна 8:

  $S=8$, значит $k = 8/2 = 4$. Найдём $N(4)$. Сумму 4 можно получить комбинациями (4, 0, 0) (3 перестановки), (3, 1, 0) (6 перестановок), (2, 2, 0) (3 перестановки), (2, 1, 1) (3 перестановки). Всего $N(4) = 3+6+3+3 = 15$. Количество счастливых билетов: $(N(4))^2 = 15^2 = 225$.

Для небольших $k$ (когда $k \le 9$), $N(k)$ можно вычислить по формуле для сочетаний с повторениями: $N(k) = \binom{k+3-1}{3-1} = \binom{k+2}{2}$.

Ответ: Если сумма всех цифр равна 0, существует 1 счастливый билет. Если сумма равна 2 – 9 билетов. Если сумма равна 4 – 36 билетов. Если сумма равна 6 – 100 билетов. Если сумма равна 8 – 225 билетов.

б) Сколько всего счастливых билетов у кассира?

Чтобы найти общее количество счастливых билетов, нужно просуммировать квадраты чисел $N(k)$ по всем возможным значениям суммы $k$. Минимальная сумма трёх цифр – 0 (0+0+0), максимальная – 27 (9+9+9). Таким образом, $k$ может принимать значения от 0 до 27.

Общее количество счастливых билетов равно $\sum_{k=0}^{27} (N(k))^2$.

Число $N(k)$ – это количество целочисленных решений уравнения $d_1+d_2+d_3 = k$ при ограничениях $0 \le d_i \le 9$. Его можно найти с помощью метода производящих функций. Формула для $N(k)$ имеет вид:

$N(k) = \binom{k+2}{2} - 3\binom{k-8}{2} + 3\binom{k-18}{2} - \binom{k-28}{2}$

где $\binom{n}{r} = 0$, если $n < r$.

Существует свойство симметрии: количество способов получить сумму $k$ равно количеству способов получить сумму $27-k$. То есть, $N(k) = N(27-k)$. Например, $N(0)=1$ и $N(27)=1$; $N(1)=3$ и $N(26)=3$.

Используя это свойство, сумму можно упростить:

$\sum_{k=0}^{27} (N(k))^2 = (N(0)^2 + ... + N(13)^2) + (N(14)^2 + ... + N(27)^2)$

Так как $N(14) = N(27-14) = N(13)$, $N(15) = N(12)$ и так далее, вторая часть суммы равна первой:

$\sum_{k=0}^{27} (N(k))^2 = 2 \sum_{k=0}^{13} (N(k))^2$

Вычислим значения $N(k)$ и $(N(k))^2$ для $k$ от 0 до 13:

• $k=0: N(0) = 1, N(0)^2=1$
• $k=1: N(1) = 3, N(1)^2=9$
• $k=2: N(2) = 6, N(2)^2=36$
• $k=3: N(3) = 10, N(3)^2=100$
• $k=4: N(4) = 15, N(4)^2=225$
• $k=5: N(5) = 21, N(5)^2=441$
• $k=6: N(6) = 28, N(6)^2=784$
• $k=7: N(7) = 36, N(7)^2=1296$
• $k=8: N(8) = 45, N(8)^2=2025$
• $k=9: N(9) = 55, N(9)^2=3025$
• $k=10: N(10) = 63, N(10)^2=3969$
• $k=11: N(11) = 69, N(11)^2=4761$
• $k=12: N(12) = 73, N(12)^2=5329$
• $k=13: N(13) = 75, N(13)^2=5625$

Теперь просуммируем квадраты:

$\sum_{k=0}^{13} (N(k))^2 = 1 + 9 + 36 + 100 + 225 + 441 + 784 + 1296 + 2025 + 3025 + 3969 + 4761 + 5329 + 5625 = 27626$.

Общее количество счастливых билетов:

$2 \times 27626 = 55252$.

Ответ: Всего у кассира 55252 счастливых билета.