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

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

a) $A$ $B$

б) $B$ $1$ $3$ $1$ $2$ $3$ $A$ $1$ $1$

в) $B$ $A$

Рис. 37

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

Метод динамического программирования:
Количество способов попасть в любой узел сетки равно сумме количества способов попасть в узел слева от него и узел снизу от него. Для всех узлов на нижней и левой границе сетки существует только один способ добраться (двигаясь только вправо или только вверх от точки А).

Комбинаторный метод:
Если для того, чтобы добраться из A в B, нужно сделать $m$ шагов вправо и $n$ шагов вверх, то общая длина любого маршрута составляет $m+n$ шагов. Задача сводится к тому, чтобы выбрать, какие из этих $m+n$ шагов будут сделаны вправо (или вверх). Количество таких способов равно числу сочетаний $C_{m+n}^m$ (или $C_{m+n}^n$).

Чтобы добраться из точки А в точку В, необходимо сделать 2 шага вправо и 2 шага вверх. Общее количество шагов: $2+2=4$.

Решение методом динамического программирования:
Обозначим через $N(i, j)$ количество путей в узел с координатами $(i, j)$, где $i$ — шаги вправо, $j$ — шаги вверх. A — это $(0,0)$, B — это $(2,2)$.

• $N(i, 0) = 1$ для $i=0, 1, 2$ (нижняя граница)
• $N(0, j) = 1$ для $j=0, 1, 2$ (левая граница)
• $N(1, 1) = N(1, 0) + N(0, 1) = 1 + 1 = 2$
• $N(2, 1) = N(2, 0) + N(1, 1) = 1 + 2 = 3$
• $N(1, 2) = N(1, 1) + N(0, 2) = 2 + 1 = 3$
• $N(2, 2) = N(2, 1) + N(1, 2) = 3 + 3 = 6$

Решение комбинаторным методом:
Нужно выбрать 2 шага вправо из 4 общих шагов. $C_{4}^2 = \frac{4!}{2!(4-2)!} = \frac{4!}{2!2!} = \frac{24}{2 \cdot 2} = 6$

Ответ: 6

Для пути из А в В нужно сделать 3 шага вправо и 2 шага вверх. Общее количество шагов: $3+2=5$.

Решение методом динамического программирования:
Цель — найти $N(3, 2)$.

• Ряд $j=0$: $N(0,0)=1, N(1,0)=1, N(2,0)=1, N(3,0)=1$
• Ряд $j=1$:
  $N(0,1)=1$
  $N(1,1) = N(1,0)+N(0,1) = 1+1=2$
  $N(2,1) = N(2,0)+N(1,1) = 1+2=3$
  $N(3,1) = N(3,0)+N(2,1) = 1+3=4$
• Ряд $j=2$:
  $N(0,2)=1$
  $N(1,2) = N(1,1)+N(0,2) = 2+1=3$
  $N(2,2) = N(2,1)+N(1,2) = 3+3=6$
  $N(3,2) = N(3,1)+N(2,2) = 4+6=10$

Решение комбинаторным методом:
Нужно выбрать 3 шага вправо из 5 общих шагов. $C_{5}^3 = \frac{5!}{3!(5-3)!} = \frac{5!}{3!2!} = \frac{120}{6 \cdot 2} = 10$

Ответ: 10

Для пути из А в В нужно сделать 4 шага вправо и 3 шага вверх. Общее количество шагов: $4+3=7$.

Решение методом динамического программирования:
Цель — найти $N(4, 3)$.

• Ряд $j=0$: $1, 1, 1, 1, 1$
• Ряд $j=1$: $1, 2, 3, 4, 5$
• Ряд $j=2$: $N(0,2)=1, N(1,2)=1+2=3, N(2,2)=3+3=6, N(3,2)=6+4=10, N(4,2)=10+5=15$
• Ряд $j=3$: $N(0,3)=1, N(1,3)=1+3=4, N(2,3)=4+6=10, N(3,3)=10+10=20, N(4,3)=20+15=35$

Решение комбинаторным методом:
Нужно выбрать 4 шага вправо из 7 общих шагов. $C_{7}^4 = \frac{7!}{4!(7-4)!} = \frac{7!}{4!3!} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$

Ответ: 35