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

1.332. Корова, выложенная из спичек, смотрит влево (рис. 35). Переложите две спички так, чтобы она смотрела вправо.

Рис. 35

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

Нужно взять эти две спички и зеркально приставить их к правой стороне туловища. Хвост коровы при этом остаётся на своём месте.

Ниже показано, какие именно спички нужно передвинуть и какой результат должен получиться.

Исходное положение:

Спички, которые нужно переложить, выделены красным цветом.

Конечное положение:

В получившейся фигуре корова смотрит вправо. Новое положение головы выделено зеленым цветом (одна из спичек головы совпала с хвостом).

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

1.333. Спички сложены, как показано на рисунке 36. Переложите 2 спички так, чтобы получилось 5 равных квадратов.

Рис. 36

Для решения этой головоломки необходимо переложить две спички, чтобы из исходной фигуры, состоящей из 4 равных квадратов, получить фигуру из 5 равных квадратов.

Анализ исходной фигуры

Исходная фигура состоит из 15 спичек и образует 4 одинаковых квадрата. Конструкцию можно описать как два столбца, в каждом из которых по два квадрата, соединенные в центре горизонтальной спичкой.

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 способов.

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