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

1.44* Докажите, что:

a) $7^n + 9$ делится на 8 для любого нечётного натурального $n$;

б) $3^n + 7$ делится на 8 для любого чётного натурального $n$.

а) Докажем, что выражение $7^n + 9$ делится на 8 для любого нечётного натурального $n$.

Для доказательства воспользуемся методом сравнений по модулю. Нам необходимо показать, что $7^n + 9 \equiv 0 \pmod{8}$.

Рассмотрим остатки от деления чисел 7 и 9 на 8:

$7 \equiv -1 \pmod{8}$

$9 \equiv 1 \pmod{8}$

Подставим эти сравнения в исходное выражение:

$7^n + 9 \equiv (-1)^n + 1 \pmod{8}$

Согласно условию, $n$ является нечётным натуральным числом. Для любого нечётного $n$ выполняется равенство $(-1)^n = -1$.

Таким образом, сравнение принимает вид:

$(-1)^n + 1 \equiv -1 + 1 \equiv 0 \pmod{8}$

Поскольку остаток от деления выражения $7^n + 9$ на 8 равен 0, это доказывает, что $7^n + 9$ делится на 8 без остатка для любого нечётного натурального $n$.

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

б) Докажем, что выражение $3^n + 7$ делится на 8 для любого чётного натурального $n$.

Также воспользуемся сравнениями по модулю. Нам необходимо показать, что $3^n + 7 \equiv 0 \pmod{8}$.

По условию, $n$ — чётное натуральное число. Это значит, что $n$ можно представить в виде $n = 2k$, где $k$ — некоторое натуральное число.

Заменим $n$ на $2k$ в исходном выражении:

$3^n + 7 = 3^{2k} + 7 = (3^2)^k + 7 = 9^k + 7$

Теперь рассмотрим полученное выражение по модулю 8:

$9^k + 7 \pmod{8}$

Найдем остаток от деления 9 на 8:

$9 \equiv 1 \pmod{8}$

Подставим это значение в наше сравнение:

$9^k + 7 \equiv 1^k + 7 \pmod{8}$

Для любого натурального числа $k$ справедливо, что $1^k = 1$. Поэтому:

$1^k + 7 \equiv 1 + 7 \equiv 8 \equiv 0 \pmod{8}$

Остаток от деления выражения $3^n + 7$ на 8 равен 0, следовательно, $3^n + 7$ делится на 8 для любого чётного натурального $n$.

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

1.45 На один из трёх штырьков насажены $n$ различных колец так, что большее кольцо лежит ниже меньшего (на рисунке 8 $n = 3$). За один ход разрешается перенести одно кольцо с одного штырька на другой, при этом не разрешается большее кольцо класть на меньшее. Докажите, что наименьшее число ходов, за которое можно перенести все кольца с одного штырька на другой, равно $2^n - 1$.

Данная задача известна как головоломка «Ханойская башня». Для доказательства того, что наименьшее число ходов, необходимое для переноса n колец, равно $2^n - 1$, мы воспользуемся методом математической индукции.

Обозначим через $H(n)$ минимальное количество ходов, необходимое для перемещения $n$ колец с одного штырька на другой, соблюдая правила.

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

Проверим утверждение для $n=1$. Чтобы перенести одно кольцо с исходного штырька на целевой, требуется ровно один ход. Согласно формуле, мы получаем: $H(1) = 2^1 - 1 = 2 - 1 = 1$. Утверждение верно для $n=1$.

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

Предположим, что для переноса $k$ колец минимально необходимое число ходов равно $H(k) = 2^k - 1$.

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

Рассмотрим задачу для $n = k+1$ колец. Нам нужно доказать, что $H(k+1) = 2^{k+1} - 1$.

Чтобы переместить самое большое, $(k+1)$-е кольцо, с исходного штырька (назовем его A) на целевой (C), необходимо, чтобы все остальные $k$ колец, которые меньше него, находились на третьем, вспомогательном штырьке (B). Это ключевое и необходимое условие, так как самое большое кольцо не может быть перемещено, если на нем есть другие кольца, и оно не может быть помещено на штырек, где уже есть меньшие кольца.

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

1. Переместить башню из верхних $k$ колец с исходного штырька (A) на вспомогательный (B), используя целевой штырек (C) как дополнительный. Согласно нашему индукционному предположению, минимальное число ходов для этой операции составляет $H(k) = 2^k - 1$.
2. Переместить самое большое, $(k+1)$-е кольцо, с исходного штырька (A) на целевой (C). Этот шаг требует ровно 1 ход.
3. Переместить башню из $k$ колец со вспомогательного штырька (B) на целевой (C), на котором уже лежит самое большое кольцо. Для этого используется исходный штырек (A) как дополнительный. Эта задача также требует $H(k) = 2^k - 1$ ходов по индукционному предположению.

Сложив количество ходов на каждом этапе, мы получим общее минимальное количество ходов для $k+1$ кольца:

$H(k+1) = H(k) + 1 + H(k) = (2^k - 1) + 1 + (2^k - 1) = 2 \cdot 2^k - 1 = 2^{k+1} - 1$.

Это доказывает, что формула верна и для $n = k+1$. Таким образом, по принципу математической индукции, мы доказали, что наименьшее число ходов, за которое можно перенести все $n$ колец с одного штырька на другой, равно $2^n - 1$.

Ответ: Утверждение, что наименьшее число ходов равно $2^n - 1$, доказано методом математической индукции.

1.46 Вычислите:

а) $5!$;

б) $6!$;

в) $\frac{7!}{5!}$;

г) $\frac{2000!}{1999!}$;

д) $\frac{15!}{10! \cdot 5!}$;

е) $\frac{12! \cdot 6!}{16!}$;

ж) $\frac{5! + 6! + 7!}{8! - 7!}$;

з) $\frac{18! - 17 \cdot 17! - 16 \cdot 16!}{17! - 16!}$.

а) По определению факториала, факториал числа $n$ (обозначается $n!$) — это произведение всех натуральных чисел от 1 до $n$ включительно.
$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 20 \cdot 6 = 120$.
Ответ: 120

б) Для вычисления $6!$ можно использовать результат предыдущего пункта, так как $6! = 6 \cdot 5!$.
$6! = 6 \cdot 120 = 720$.
Ответ: 720

в) Для упрощения дроби используем свойство $n! = n \cdot (n-1)!$.
Разложим числитель: $7! = 7 \cdot 6 \cdot 5!$.
$\frac{7!}{5!} = \frac{7 \cdot 6 \cdot 5!}{5!}$.
Сокращаем $5!$ в числителе и знаменателе:
$7 \cdot 6 = 42$.
Ответ: 42

г) По аналогии с предыдущим примером, разложим $2000!$ как $2000 \cdot 1999!$.
$\frac{2000!}{1999!} = \frac{2000 \cdot 1999!}{1999!}$.
Сокращаем $1999!$ и получаем:
$2000$.
Ответ: 2000

д) Данное выражение является биномиальным коэффициентом $C_{15}^5$. Для вычисления разложим факториалы.
$\frac{15!}{10! \cdot 5!} = \frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10!}{10! \cdot 5!}$.
Сократим $10!$:
$\frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{5!} = \frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}$.
Произведем сокращения: $\frac{15}{5 \cdot 3} = 1$; $\frac{12}{4} = 3$; $\frac{14}{2} = 7$.
В результате получаем: $1 \cdot 7 \cdot 13 \cdot 3 \cdot 11 = 7 \cdot 13 \cdot 33 = 91 \cdot 33 = 3003$.
Ответ: 3003

е) Разложим больший факториал в знаменателе, чтобы сократить дробь.
$16! = 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12!$.
$\frac{12! \cdot 6!}{16!} = \frac{12! \cdot 6!}{16 \cdot 15 \cdot 14 \cdot 13 \cdot 12!}$.
Сокращаем $12!$:
$\frac{6!}{16 \cdot 15 \cdot 14 \cdot 13}$.
Знаем, что $6! = 720$.
$\frac{720}{16 \cdot 15 \cdot 14 \cdot 13} = \frac{720}{240 \cdot 14 \cdot 13} = \frac{3}{14 \cdot 13} = \frac{3}{182}$.
Ответ: $\frac{3}{182}$

ж) Для упрощения выражения вынесем общие множители за скобки в числителе и знаменателе.
В числителе вынесем наименьший факториал $5!$:
$5! + 6! + 7! = 5! + 6 \cdot 5! + 7 \cdot 6 \cdot 5! = 5! \cdot (1 + 6 + 42) = 5! \cdot 49$.
В знаменателе вынесем $7!$:
$8! - 7! = 8 \cdot 7! - 7! = 7! \cdot (8 - 1) = 7! \cdot 7$.
Подставим упрощенные выражения в дробь:
$\frac{5! \cdot 49}{7! \cdot 7} = \frac{5! \cdot 49}{(7 \cdot 6 \cdot 5!) \cdot 7}$.
Сократим $5!$ и преобразуем: $\frac{49}{7 \cdot 6 \cdot 7} = \frac{49}{42 \cdot 7} = \frac{49}{294}$.
Сократим дробь на 49: $\frac{49}{49 \cdot 6} = \frac{1}{6}$.
Ответ: $\frac{1}{6}$

з) Упростим числитель и знаменатель по отдельности. Для этого будем приводить все к наименьшему факториалу $16!$.
Знаменатель: $17! - 16! = 17 \cdot 16! - 16! = (17 - 1) \cdot 16! = 16 \cdot 16!$.
Числитель: $18! - 17 \cdot 17! - 16 \cdot 16!$.
Сначала упростим первую часть числителя: $18! - 17 \cdot 17! = 18 \cdot 17! - 17 \cdot 17! = (18 - 17) \cdot 17! = 1 \cdot 17! = 17!$.
Теперь числитель имеет вид: $17! - 16 \cdot 16!$.
Упростим это выражение: $17 \cdot 16! - 16 \cdot 16! = (17 - 16) \cdot 16! = 1 \cdot 16! = 16!$.
Итак, исходная дробь равна:
$\frac{16!}{16 \cdot 16!}$.
Сокращаем $16!$ и получаем $\frac{1}{16}$.
Ответ: $\frac{1}{16}$