Номер 321, страница 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