Страница 42, часть 2 - гдз по алгебре 10 класс учебник часть 1, 2 Мордкович, Семенов

Докажите, что количество разных наборов по два предмета, которые можно сделать из $n$ различных предметов $(n \ge 2)$, равно $ \frac{n \cdot (n - 1)}{2} $.

б) Докажите, что количество разных наборов по три предмета, которые можно сделать из $n$ различных предметов $(n \ge 3)$, равно $ \frac{n \cdot (n - 1) \cdot (n - 2)}{6} $.

а)

Задача состоит в том, чтобы найти количество различных наборов по два предмета, которые можно составить из $n$ различных предметов. В таких наборах порядок элементов не имеет значения, поэтому речь идет о нахождении числа сочетаний из $n$ элементов по 2.

Рассмотрим процесс выбора двух предметов последовательно:

1. Первый предмет из $n$ имеющихся можно выбрать $n$ способами.

2. После того как первый предмет выбран, для выбора второго остается $n-1$ предмет. Следовательно, второй предмет можно выбрать $n-1$ способом.

Если бы порядок выбора был важен, мы бы получили $n \cdot (n-1)$ различных упорядоченных пар. Такие упорядоченные наборы называются размещениями.

Однако в задаче требуется найти количество наборов, где порядок не важен. Это означает, что набор, состоящий, например, из предмета A и предмета B, идентичен набору из предмета B и предмета A. При подсчете упорядоченных пар мы учли каждый такой набор ровно два раза: как (A, B) и как (B, A). Количество способов упорядочить два элемента равно числу их перестановок, то есть $2! = 2 \cdot 1 = 2$.

Чтобы найти истинное количество уникальных наборов (сочетаний), нужно общее количество упорядоченных пар разделить на количество перестановок в каждой паре:

Количество наборов = $\frac{n \cdot (n-1)}{2}$.

Это соответствует общей формуле для числа сочетаний $C_n^k = \frac{n!}{k!(n-k)!}$ при $k=2$:

$C_n^2 = \frac{n!}{2!(n-2)!} = \frac{n \cdot (n-1) \cdot (n-2)!}{2 \cdot 1 \cdot (n-2)!} = \frac{n \cdot (n-1)}{2}$.

Таким образом, утверждение доказано.

Ответ: Доказательство основано на подсчете упорядоченных пар предметов, которых можно выбрать $n \cdot (n-1)$ способами. Так как порядок в наборе не важен, это число делится на $2! = 2$ (число перестановок двух элементов), что и приводит к формуле $\frac{n \cdot (n-1)}{2}$.

б)

Аналогично пункту а), нам нужно доказать формулу для количества наборов по три предмета из $n$ различных предметов. Это задача на нахождение числа сочетаний из $n$ элементов по 3.

Рассмотрим последовательный выбор трех предметов:

1. Первый предмет можно выбрать $n$ способами.

2. Второй предмет можно выбрать из оставшихся $n-1$ предметов, то есть $n-1$ способом.

3. Третий предмет можно выбрать из оставшихся $n-2$ предметов, то есть $n-2$ способами.

Общее число упорядоченных наборов из трех предметов (размещений) равно произведению числа способов на каждом шаге: $n \cdot (n-1) \cdot (n-2)$.

Поскольку порядок предметов в наборе не важен, мы должны учесть, что каждый уникальный набор из трех предметов (например, {A, B, C}) был посчитан несколько раз в виде разных упорядоченных последовательностей ( (A, B, C), (A, C, B), (B, A, C) и т.д. ). Количество способов, которыми можно упорядочить три предмета, равно числу их перестановок:

$3! = 3 \cdot 2 \cdot 1 = 6$.

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

Количество наборов = $\frac{n \cdot (n-1) \cdot (n-2)}{6}$.

Данный результат также следует из общей формулы для числа сочетаний $C_n^k$ при $k=3$:

$C_n^3 = \frac{n!}{3!(n-3)!} = \frac{n \cdot (n-1) \cdot (n-2) \cdot (n-3)!}{3 \cdot 2 \cdot 1 \cdot (n-3)!} = \frac{n \cdot (n-1) \cdot (n-2)}{6}$.

Таким образом, утверждение доказано.

Ответ: Доказательство основано на том, что количество упорядоченных троек, выбираемых из $n$ элементов, равно $n \cdot (n-1) \cdot (n-2)$. Поскольку порядок в наборе не важен, это число делится на $3! = 6$ (число перестановок трех элементов), что приводит к искомой формуле $\frac{n \cdot (n-1) \cdot (n-2)}{6}$.

6.25. a) Докажите, что количество разных непустых наборов, которые можно сделать из $n$ различных предметов, равно $2^n - 1$.

б) Докажите, что $n$ различных предметов можно расставить в ряд $n!$ способами.

а) Докажем это утверждение с помощью комбинаторных рассуждений.
Пусть у нас есть множество, состоящее из $n$ различных предметов. При формировании любого набора (подмножества) для каждого из $n$ предметов существует ровно два варианта: либо этот предмет входит в набор, либо не входит.
Поскольку выбор для каждого предмета независим от выбора для других предметов, общее количество возможных наборов можно найти, перемножив количество вариантов для каждого предмета. Так как предметов $n$, а для каждого есть 2 варианта, общее число всех возможных наборов (включая пустой) равно:
$2 \cdot 2 \cdot \dots \cdot 2$ ($n$ раз) = $2^n$.
Эта формула включает в себя один случай, когда мы не выбираем ни одного предмета, то есть получаем пустой набор. В условии задачи сказано, что нужно найти количество непустых наборов. Следовательно, из общего числа всех возможных наборов нужно вычесть один случай, соответствующий пустому набору.
Таким образом, количество разных непустых наборов равно $2^n - 1$.

Альтернативное доказательство через биномиальные коэффициенты:
Количество способов выбрать $k$ предметов из $n$ равно биномиальному коэффициенту $\binom{n}{k}$. Чтобы найти общее количество непустых наборов, нужно сложить количество наборов всех возможных размеров от 1 до $n$:
Сумма = $\binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n}$.
Известна формула бинома Ньютона: $\sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$.
Поскольку $\binom{n}{0} = 1$ (это и есть пустой набор), то искомая сумма равна:
$(\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n}) - \binom{n}{0} = 2^n - 1$.
Оба способа приводят к одному и тому же результату.
Ответ: Количество разных непустых наборов, которые можно составить из $n$ различных предметов, действительно равно $2^n - 1$.

б) Докажем это утверждение, используя основное правило комбинаторики (правило умножения).
Задача состоит в том, чтобы разместить $n$ различных предметов на $n$ позициях в ряду. Такое упорядоченное расположение называется перестановкой.
Рассмотрим процесс заполнения позиций поочередно:

• На первую позицию в ряду мы можем поставить любой из $n$ предметов. Таким образом, у нас есть $n$ вариантов выбора.
• После того как мы поставили один предмет на первую позицию, у нас осталось $n-1$ предметов. На вторую позицию мы можем поставить любой из оставшихся $n-1$ предметов. Значит, для второй позиции есть $n-1$ вариант.
• Для третьей позиции, соответственно, останется $n-2$ предмета, то есть $n-2$ варианта.
• ...
• Этот процесс продолжается до последней, $n$-ой позиции. К этому моменту останется только один предмет, поэтому для последней позиции существует всего 1 вариант.

Согласно правилу умножения, общее количество способов расставить все предметы равно произведению числа вариантов для каждой позиции:
$N = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 2 \cdot 1$.
Это произведение по определению является факториалом числа $n$ и обозначается как $n!$.
Таким образом, существует $n!$ различных способов расставить $n$ различных предметов в ряд.
Ответ: $n$ различных предметов можно расставить в ряд $n!$ способами.

6.26. Докажите, что любое натуральное число $h > 4$ можно представить в виде $h = 3m + 5n$, где $m$ и $n$ — целые числа.

Требуется доказать, что любое натуральное число $h > 4$ можно представить в виде $h = 3m + 5n$, где $m$ и $n$ — целые числа. Это эквивалентно доказательству утверждения для всех натуральных чисел $h \ge 5$.

Сначала рассмотрим несколько примеров для первых чисел, удовлетворяющих условию:

• Для $h=5$: $5 = 3 \cdot 0 + 5 \cdot 1$. Представление найдено при $m=0, n=1$.
• Для $h=6$: $6 = 3 \cdot 2 + 5 \cdot 0$. Представление найдено при $m=2, n=0$.
• Для $h=7$: $7 = 3 \cdot (-1) + 5 \cdot 2$. Представление найдено при $m=-1, n=2$.
• Для $h=8$: $8 = 3 \cdot 1 + 5 \cdot 1$. Представление найдено при $m=1, n=1$.

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

База индукции

Проверим утверждение для наименьшего натурального числа, удовлетворяющего условию $h > 4$, то есть для $h=5$. Как мы уже видели, $5 = 3 \cdot 0 + 5 \cdot 1$. Коэффициенты $m=0$ и $n=1$ являются целыми числами, поэтому база индукции верна.

Шаг индукции

Предположим, что для некоторого натурального числа $k \ge 5$ утверждение верно, то есть существуют такие целые числа $m_k$ и $n_k$, что выполняется равенство:
$k = 3m_k + 5n_k$

Теперь докажем, что утверждение справедливо и для следующего натурального числа, $k+1$. Нам нужно показать, что существуют целые числа $m_{k+1}$ и $n_{k+1}$, для которых $k+1 = 3m_{k+1} + 5n_{k+1}$.

Для этого представим число 1 как линейную комбинацию чисел 3 и 5. Например, справедливо следующее равенство:
$1 = 3 \cdot 2 + 5 \cdot (-1)$

Прибавим это представление единицы к обеим частям нашего индуктивного предположения:
$k+1 = (3m_k + 5n_k) + 1$
$k+1 = (3m_k + 5n_k) + (3 \cdot 2 + 5 \cdot (-1))$

Теперь сгруппируем слагаемые с общими множителями 3 и 5:
$k+1 = (3m_k + 3 \cdot 2) + (5n_k + 5 \cdot (-1))$
$k+1 = 3(m_k + 2) + 5(n_k - 1)$

Мы получили искомое представление для $k+1$. Если мы обозначим $m_{k+1} = m_k + 2$ и $n_{k+1} = n_k - 1$, то поскольку $m_k$ и $n_k$ по предположению являются целыми числами, их суммы и разности $m_{k+1}$ и $n_{k+1}$ также будут целыми числами.

Таким образом, мы доказали, что если утверждение верно для числа $k$, то оно верно и для числа $k+1$.

Так как база индукции ($h=5$) верна и индукционный переход доказан, по принципу математической индукции утверждение справедливо для всех натуральных чисел $h \ge 5$, то есть для всех $h > 4$.

Ответ: Утверждение доказано.

6.27. Докажите методом математической индукции, что у выпуклого $n$-угольника $(n \ge 3)$:

a) сумма внутренних углов равна $180^\circ(n - 2)$;

б) число диагоналей равно $\frac{n(n - 3)}{2}$.

а) сумма внутренних углов равна $180^\circ(n-2)$

Докажем данное утверждение методом математической индукции по числу сторон $n$, где $n \ge 3$.

1. База индукции.

Проверим утверждение для наименьшего возможного значения $n=3$. Для треугольника ($n=3$) сумма внутренних углов, как известно из геометрии, равна $180^\circ$.

Подставим $n=3$ в данную формулу:

$S_3 = 180^\circ(3-2) = 180^\circ \cdot 1 = 180^\circ$.

Формула верна для $n=3$. База индукции доказана.

2. Индукционное предположение.

Предположим, что формула верна для некоторого натурального числа $k \ge 3$. То есть, мы считаем, что сумма внутренних углов любого выпуклого $k$-угольника равна $S_k = 180^\circ(k-2)$.

3. Индукционный шаг.

Докажем, что если утверждение верно для $n=k$, то оно верно и для $n=k+1$. То есть, нам нужно доказать, что сумма углов выпуклого $(k+1)$-угольника равна $S_{k+1} = 180^\circ((k+1)-2) = 180^\circ(k-1)$.

Рассмотрим выпуклый $(k+1)$-угольник с вершинами $A_1, A_2, \dots, A_k, A_{k+1}$. Проведём в нём диагональ, соединяющую вершины $A_1$ и $A_k$. Поскольку многоугольник выпуклый, эта диагональ будет лежать полностью внутри него и разделит его на два многоугольника:

• Выпуклый $k$-угольник с вершинами $A_1, A_2, \dots, A_k$.
• Треугольник $\triangle A_1A_kA_{k+1}$.

Сумма внутренних углов $(k+1)$-угольника будет равна сумме внутренних углов этих двух многоугольников.

Сумма углов треугольника $\triangle A_1A_kA_{k+1}$ равна $180^\circ$.

Сумма углов $k$-угольника $A_1A_2...A_k$, согласно нашему индукционному предположению, равна $S_k = 180^\circ(k-2)$.

Следовательно, общая сумма углов $(k+1)$-угольника равна:

$S_{k+1} = S_k + 180^\circ = 180^\circ(k-2) + 180^\circ = 180^\circ(k-2+1) = 180^\circ(k-1)$.

Мы получили в точности формулу для $n=k+1$. Таким образом, индукционный переход доказан.

По принципу математической индукции, формула верна для любого выпуклого $n$-угольника при $n \ge 3$.

Ответ: Утверждение доказано.

б) число диагоналей равно $\frac{n(n-3)}{2}$

Докажем данное утверждение методом математической индукции по числу сторон $n$, где $n \ge 3$. Обозначим число диагоналей $n$-угольника как $D_n$.

1. База индукции.

Проверим утверждение для $n=3$. У треугольника ($n=3$) нет диагоналей, то есть $D_3=0$.

Подставим $n=3$ в формулу:

$D_3 = \frac{3(3-3)}{2} = \frac{3 \cdot 0}{2} = 0$.

Формула верна для $n=3$. База индукции доказана.

2. Индукционное предположение.

Предположим, что формула верна для некоторого натурального числа $k \ge 3$. То есть, число диагоналей выпуклого $k$-угольника равно $D_k = \frac{k(k-3)}{2}$.

3. Индукционный шаг.

Докажем, что если утверждение верно для $n=k$, то оно верно и для $n=k+1$. Нам нужно доказать, что $D_{k+1} = \frac{(k+1)((k+1)-3)}{2} = \frac{(k+1)(k-2)}{2}$.

Рассмотрим выпуклый $(k+1)$-угольник $A_1A_2...A_kA_{k+1}$.

Его диагонали можно разделить на три группы:

1. Диагонали $k$-угольника $A_1A_2...A_k$. По индукционному предположению, их число равно $D_k = \frac{k(k-3)}{2}$.
2. Диагонали, которые соединяют новую вершину $A_{k+1}$ с остальными вершинами. Из вершины $A_{k+1}$ можно провести диагонали ко всем вершинам, кроме самой себя и двух соседних ($A_1$ и $A_k$). Таким образом, из $A_{k+1}$ можно провести $(k+1) - 3 = k-2$ диагонали.
3. Отрезок $A_1A_k$, который был стороной в $k$-угольнике $A_1A_2...A_k$, в $(k+1)$-угольнике является диагональю, так как вершины $A_1$ и $A_k$ не являются соседними (между ними находится вершина $A_{k+1}$). Это еще одна, ранее не учтенная, диагональ.

Суммируем количество диагоналей:

$D_{k+1} = D_k + (k-2) + 1 = \frac{k(k-3)}{2} + k-1$.

Приведём выражение к общему знаменателю и упростим:

$D_{k+1} = \frac{k(k-3) + 2(k-1)}{2} = \frac{k^2 - 3k + 2k - 2}{2} = \frac{k^2 - k - 2}{2}$.

Разложим числитель на множители. Корнями уравнения $k^2 - k - 2 = 0$ являются $k=2$ и $k=-1$. Поэтому $k^2 - k - 2 = (k-2)(k+1)$.

Следовательно, $D_{k+1} = \frac{(k+1)(k-2)}{2}$.

Это совпадает с формулой для $n=k+1$. Индукционный переход доказан.

По принципу математической индукции, формула верна для любого выпуклого $n$-угольника при $n \ge 3$.

Ответ: Утверждение доказано.