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

a) B A

б) 1 3 B 1 2 3 A 1 1

в) B A

Рис. 34

321. Из точки А, показанной на схеме города, надо попасть в точку В, двигаясь только вправо и вверх. На рисунке 34, а показан один из маршрутов движения. Убедитесь, что это можно сделать только 6 способами.

Чтобы убедиться, что различных маршрутов движения от А к В только 6, можно их нарисовать по отдельности. Мы поступим проще. Укажем в каждой точке, в которой можно изменить направление движения, число способов, которыми можно прийти в эту точку (рис. 34, б). В точку В можно прийти $3 + 3 = 6$ способами.

Задача состоит в том, чтобы найти количество различных маршрутов из точки А в точку В, если разрешено двигаться только вправо и вверх.

Чтобы переместиться из точки А в точку В на показанной схеме, необходимо совершить 2 перемещения вправо и 2 перемещения вверх. Общее количество перемещений в любом маршруте будет равно 4. Убедимся, что существует ровно 6 таких маршрутов, используя два различных подхода.

Способ 1: Комбинаторный

Каждый маршрут представляет собой уникальную последовательность из 4 шагов, среди которых 2 шага "вправо" (обозначим П) и 2 шага "вверх" (обозначим В). Например, последовательность ППВВ означает два шага вправо, а затем два шага вверх.

Задача сводится к тому, чтобы найти количество способов расположить 2 шага "вправо" (или 2 шага "вверх") в последовательности из 4 шагов. Это классическая задача на сочетания, которая решается по формуле:

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

где $n$ — общее количество шагов, а $k$ — количество шагов одного типа (например, вправо).

В нашем случае $n = 4$ и $k = 2$. Подставим эти значения в формулу:

$C_4^2 = \frac{4!}{2!(4-2)!} = \frac{4!}{2!2!} = \frac{4 \times 3 \times 2 \times 1}{(2 \times 1)(2 \times 1)} = \frac{24}{4} = 6$.

Таким образом, существует 6 различных маршрутов.

Способ 2: Метод динамического программирования (как на рис. 34, б)

Этот метод заключается в последовательном подсчете количества способов добраться до каждого перекрестка на схеме.

1. В начальную точку А можно попасть одним способом (это точка старта).

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

Применим это правило к нашей сетке, расставив числа на перекрестках:

- В перекрестки, которые находятся на расстоянии одного шага от А (вправо или вверх), можно попасть только одним способом.

- В центральный перекресток можно попасть из левого (1 способ) и из нижнего (1 способ). Итого: $1 + 1 = 2$ способа.

- В перекресток справа от центрального можно попасть из центрального (2 способа) и из нижнего (1 способ). Итого: $2 + 1 = 3$ способа.

- Аналогично, в перекресток над центральным можно попасть из центрального (2 способа) и из левого (1 способ). Итого: $2 + 1 = 3$ способа.

- Наконец, в конечную точку В можно попасть из перекрестка слева (куда ведут 3 способа) и из перекрестка снизу (куда также ведут 3 способа). Общее количество способов: $3 + 3 = 6$.

Оба метода подтверждают, что из точки А в точку В, двигаясь только вправо и вверх, можно добраться шестью различными способами.

Ответ: 6

322. Если мы захотим показать все маршруты движения (только вправо и вверх) из A в B (рис. 34, в), то придётся много потрудиться. Гораздо проще подсчитать их число описанным выше способом. Подсчитайте.

Для решения задачи необходимо подсчитать количество кратчайших маршрутов из начальной точки A в конечную точку B на прямоугольной сетке, двигаясь только вправо и вверх. Исходя из контекста подобных задач, можно предположить, что сетка имеет размер 4 на 3 клетки. Это означает, что для перемещения из левого нижнего угла (точка А) в правый верхний (точка В) необходимо совершить 4 шага вправо и 3 шага вверх.

Способ 1: Комбинаторный метод

Каждый маршрут из А в В состоит из $4 + 3 = 7$ шагов. Из этих 7 шагов 4 должны быть сделаны вправо, а 3 — вверх. Задача сводится к нахождению числа всех возможных уникальных последовательностей из 4 шагов вправо и 3 шагов вверх. Это классическая задача на число сочетаний: нам нужно выбрать 3 позиции для шагов «вверх» из 7 общих позиций (или, что то же самое, 4 позиции для шагов «вправо»).

Число сочетаний вычисляется по формуле:

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

Здесь $n=7$ — общее количество шагов, а $k=3$ — количество шагов вверх.

Подставим значения в формулу:

$C_7^3 = \frac{7!}{3!(7-3)!} = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5 \times 4!}{3 \times 2 \times 1 \times 4!} = \frac{7 \times 6 \times 5}{6} = 35$

Способ 2: Динамическое программирование (метод, упомянутый в условии)

Этот метод заключается в том, чтобы для каждого перекрестка на сетке вычислить, сколькими способами до него можно добраться.В начальную точку А ведет 1 путь (мы уже там). До любого перекрестка на нижней границе сетки можно дойти только одним способом — двигаясь вправо. То же самое касается левой границы — до любого перекрестка на ней можно дойти только одним способом, двигаясь вверх.Количество путей до любого другого перекрестка равно сумме количества путей до перекрестка, расположенного слева, и количества путей до перекрестка, расположенного снизу.

Применяя этот принцип, мы последовательно заполняем всю сетку числами. В результате для конечной точки B мы получим число 35.

Например, для сетки узлов (где A - узел (0,0), а B - узел (4,3)):

• Количество путей до узлов $(i,0)$ равно 1.
• Количество путей до узлов $(0,j)$ равно 1.
• Количество путей до узла $(1,1)$ равно $1+1=2$.
• Количество путей до узла $(2,1)$ равно $2+1=3$.
• ...
• Количество путей до узла $(4,2)$ равно $10+5=15$.
• Количество путей до узла $(3,3)$ равно $10+10=20$.
• Количество путей до конечного узла B $(4,3)$ равно сумме путей до узла слева $(3,3)$ и узла снизу $(4,2)$, то есть $20 + 15 = 35$.

Оба метода дают одинаковый результат.

Ответ: 35

323. Коля написал два раза своё имя (рис. 35, а). Его сосед по парте заметил, что Коля может прочитать своё имя более чем 10 способами, и показал один из них (рис. 35, б). Сколькими способами Коля может прочитать своё имя?

а) К О Л Я
К О Л Я

б) К—О. Л
К О Л-Я

Рис. 35

Чтобы прочитать имя "КОЛЯ", необходимо последовательно выбрать по одной букве из каждого столбца, двигаясь слева направо. Для каждой буквы в имени "КОЛЯ" нужно определить, сколько вариантов выбора существует.

• Выбор буквы "К": В первом столбце есть две буквы "К" (в верхней и нижней строке). Следовательно, есть 2 способа выбрать первую букву.
• Выбор буквы "О": Во втором столбце также находятся две буквы "О". Выбор этой буквы не зависит от выбора предыдущей, поэтому для нее тоже есть 2 способа.
• Выбор буквы "Л": Аналогично, для третьей буквы "Л" есть 2 способа выбора.
• Выбор буквы "Я": Для последней буквы "Я" также есть 2 способа выбора.

Согласно комбинаторному правилу произведения, общее количество способов составить слово равно произведению количества вариантов выбора для каждой буквы. Таким образом, общее число способов прочитать имя "КОЛЯ" равно:

$2 \times 2 \times 2 \times 2 = 2^4 = 16$

Это число (16) больше 10, что соответствует условию задачи.

Ответ: 16 способами.

324. На рисунке 36 показано, как можно прочитать слово «МАРШРУТ». Подсчитайте число всех способов, которыми можно прочитать это слово.

a) КОЛЯ
КОЛЯ

б) К-О-Л-Я
К О Л-Я

Рис. 35

Рис. 36

Для решения этой комбинаторной задачи необходимо подсчитать количество путей на схеме, которые образуют слово «МАРШРУТ». Схема представляет собой последовательность условных столбцов с буквами. Чтобы прочитать слово, нужно последовательно переходить от буквы в одном столбце к букве в следующем. Судя по расположению букв и показанному примеру, переход возможен только к соседней по вертикали букве в следующем столбце.

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

Для первой буквы «М» мы можем начать с любой из трех предложенных. Таким образом, количество способов для каждой из них (сверху вниз) равно [1, 1, 1].

Для второй буквы «А» количество способов добраться до каждой из них равно сумме способов добраться до соседних букв «М» из предыдущего столбца:

• Верхняя «А»: $1 + 1 = 2$ способа.
• Нижняя «А»: $1 + 1 = 2$ способа.

Итог для «А»: [2, 2].

Для третьей буквы «Р»:

• Верхняя «Р»: $2$ способа.
• Средняя «Р»: $2 + 2 = 4$ способа.
• Нижняя «Р»: $2$ способа.

Итог для «Р»: [2, 4, 2].

Для четвертой буквы «Ш»:

• Верхняя «Ш»: $2 + 4 = 6$ способов.
• Нижняя «Ш»: $4 + 2 = 6$ способов.

Итог для «Ш»: [6, 6].

Для пятой буквы «Р»:

• Верхняя «Р»: $6$ способов.
• Средняя «Р»: $6 + 6 = 12$ способов.
• Нижняя «Р»: $6$ способов.

Итог для «Р»: [6, 12, 6].

Для шестой буквы «У»:

• Верхняя «У»: $6 + 12 = 18$ способов.
• Нижняя «У»: $12 + 6 = 18$ способов.

Итог для «У»: [18, 18].

Для седьмой буквы «Т»:

• Верхняя «Т»: $18$ способов.
• Средняя «Т»: $18 + 18 = 36$ способов.
• Нижняя «Т»: $18$ способов.

Итог для «Т»: [18, 36, 18].

Общее число способов прочитать слово «МАРШРУТ» равно сумме всех способов, которыми можно закончить слово на любой из букв «Т» в последнем столбце: $18 + 36 + 18 = 72$.

Ответ: 72