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

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