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

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

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

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

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

1. Комбинаторный метод.

Пусть для достижения точки В из точки А необходимо сделать $m$ шагов вправо и $n$ шагов вверх. Общая длина любого такого маршрута составит $m+n$ шагов. Количество различных маршрутов будет равно количеству способов расположить $m$ шагов «вправо» среди $m+n$ общих шагов. Это классическая задача на сочетания, и ее решение дается формулой числа сочетаний:

$C_{m+n}^m = \frac{(m+n)!}{m!n!}$

Из условия задачи известно, что общее количество способов равно 6. Подберем такие целые числа $m$ и $n$, чтобы результат вычисления по формуле был равен 6. Если предположить, что схема города представляет собой сетку 2x2 квартала, то для перемещения из левого нижнего угла (А) в правый верхний (В) потребуется сделать $m=2$ шага вправо и $n=2$ шага вверх. Проверим это предположение:

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

Результат совпал с условием. Это подтверждает, что маршрут состоит из 4 шагов: 2 вправо (П) и 2 вверх (В). Все 6 возможных комбинаций можно перечислить: ППВВ, ПВПВ, ПВВП, ВППВ, ВПВП, ВВПП.

2. Метод динамического программирования (описанный в учебнике).

Этот метод заключается в последовательном расчете количества способов добраться до каждого перекрестка (узла) сетки. Количество способов добраться до любого перекрестка равно сумме количества способов добраться до соседнего перекрестка слева и соседнего перекрестка снизу (так как в каждый узел можно прийти только из этих двух направлений).

Представим нашу сетку 2x2 (которая имеет 3x3 перекрестка) и рассчитаем количество путей для каждого узла, двигаясь от A к B:

• В начальную точку А есть только 1 способ попасть — это начало пути.
• Во все точки на нижней границе (кроме А) можно попасть только из А, двигаясь вправо. Значит, в каждую из них ведет 1 путь.
• Аналогично, во все точки на левой границе (кроме А) можно попасть только из А, двигаясь вверх. В каждую из них также ведет 1 путь.
• Количество путей в центральный перекресток равно сумме путей в точку слева (1) и точку снизу (1): $1+1=2$ способа.
• В точку слева от В можно прийти из точки снизу (2 способа) и точки слева от нее (1 способ): $2+1=3$ способа.
• В точку снизу от В можно прийти из точки слева (2 способа) и точки снизу от нее (1 способ): $2+1=3$ способа.
• Наконец, в конечную точку В можно прийти из точки слева (3 способа) и из точки снизу (3 способа). Общее число способов: $3+3=6$.

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

Ответ: 6 способов.