Подсчёт маршрутов

  • 4 мин чтения
  • Послушать — 3 мин
  • 10 карточек

Математика, 5 класс · С. М. Никольский, М. К. Потапов, Н. Н. Решетников, А. В. Шевкин

Если двигаться можно только вправо и вверх (или вправо и вниз), число путей в каждую точку считают без перебора:

  • в точки нижнего ряда и левого столбца ведёт ровно 1 путь;
  • в любую другую точку можно прийти либо слева, либо снизу, поэтому число путей в неё равно сумме чисел в соседней точке слева и в соседней точке снизу.
136
123
111

Так в верхний правый угол квадрата 2 × 2 ведут 6 путей.

Так же считают, сколькими способами можно прочитать слово, если от каждой буквы можно перейти к следующей вправо или вниз: в каждой клетке пиши число способов дойти до неё.

Зачем это

1 / 10

Сколько путей?

Из точки A в точку B идут по линиям сетки, двигаясь только вправо и вверх. Сколько разных путей?

Перебирать пути долго и легко сбиться. Их можно посчитать без перебора — по точкам.

Правило

2 / 10

По краю — один путь

В точки нижнего ряда и левого столбца ведёт ровно 1 путь: туда можно идти только прямо — только вправо или только вверх.

Правило

3 / 10

Сумма соседей

В любую другую точку можно прийти либо слева, либо снизу. Поэтому число путей в неё равно сумме чисел в соседней точке слева и в соседней точке снизу.

Слева 3 пути, снизу 3 пути — в точку 3 + 3 = 6 путей.

Проверь себя

4 / 10

Сколько путей в точку?

Число путей = слева + снизу.

В соседнюю точку слева ведут 4 пути, в соседнюю снизу — 6. Сколько путей в эту точку?

10246
Ответ и объяснение

4 + 6 = 10 путей.

Разбор

5 / 10

Считаем по точкам

Сколько путей из A в B по сетке 3 × 2 клетки (3 шага вправо, 2 вверх)?

  1. Край

    Нижний ряд и левый столбец: по 1.

  2. Средний ряд

    1 + 1 = 2, 2 + 1 = 3, 3 + 1 = 4.

  3. Верхний ряд

    1 + 2 = 3, 3 + 3 = 6, 6 + 4 = 10.

  4. Ответ

    10 путей.

    Сетка 3 на 2 клетки от точки A слева внизу до точки B справа вверху. У перекрёстков числа путей: нижний ряд 1, 1, 1, 1; средний 1, 2, 3, 4; верхний 1, 3, 6, 10
    Сетка 3 на 2 клетки от точки A слева внизу до точки B справа вверху. У перекрёстков числа путей: нижний ряд 1, 1, 1, 1; средний 1, 2, 3, 4; верхний 1, 3, 6, 10

Частая ошибка

6 / 10

Перемножили соседей

Ошибка: в угол квадрата 2 × 2 ведут 3 · 3 = 9 путей.

Верно: 3 + 3 = 6.

Проверка перебором (П — вправо, В — вверх): ППВВ, ПВПВ, ПВВП, ВППВ, ВПВП, ВВПП — ровно 6.

Правило

7 / 10

Вправо и вниз

Если идти можно вправо и вниз (из левого верхнего угла), всё так же, только:

  • по 1 пути — в точки верхнего ряда и левого столбца;
  • в другую точку — сумма чисел слева и сверху.
111
123
136

Правило

8 / 10

Сколькими способами прочитать

Так же считают, сколькими способами можно прочитать слово, переходя к следующей букве вправо или вниз. В каждую клетку пиши, сколькими способами до неё дойти:

ГОР
ОРО
РОД

Числа те же, что в таблице путей: до буквы Д — 6 способов.

Проверь себя

9 / 10

Сколькими способами?

ЛУН
УНА

Пиши числа в клетки, начиная с первой буквы.

Сколькими способами можно прочитать ЛУНА, переходя вправо или вниз?

324
Ответ и объяснение

Числа в нижнем ряду: 1, 2, 3 — до буквы А три способа.

Главное

10 / 10

Главное

  • По краю, откуда начинаем, — по 1 пути.
  • В другую точку — сумма чисел двух соседей, откуда в неё приходят.
  • Квадрат 2 × 2 — 6 путей; сетка 3 × 2 — 10.
  • Слово читают так же: в клетке — число способов дойти до неё.

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест