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

324. На рисунке 36 показано, как можно прочитать слово «МАРШРУТ». Подсчитайте число всех способов, которыми можно прочитать это слово.

a) КОЛЯ
КОЛЯ

б) К-О-Л-Я
К О Л-Я

Рис. 35

Рис. 36

Для решения этой комбинаторной задачи необходимо подсчитать количество путей на схеме, которые образуют слово «МАРШРУТ». Схема представляет собой последовательность условных столбцов с буквами. Чтобы прочитать слово, нужно последовательно переходить от буквы в одном столбце к букве в следующем. Судя по расположению букв и показанному примеру, переход возможен только к соседней по вертикали букве в следующем столбце.

Будем решать задачу методом динамического программирования, пошагово вычисляя количество способов составить начало слова, заканчивающееся на каждую из букв в очередном столбце.

Для первой буквы «М» мы можем начать с любой из трех предложенных. Таким образом, количество способов для каждой из них (сверху вниз) равно [1, 1, 1].

Для второй буквы «А» количество способов добраться до каждой из них равно сумме способов добраться до соседних букв «М» из предыдущего столбца:

• Верхняя «А»: $1 + 1 = 2$ способа.
• Нижняя «А»: $1 + 1 = 2$ способа.

Итог для «А»: [2, 2].

Для третьей буквы «Р»:

• Верхняя «Р»: $2$ способа.
• Средняя «Р»: $2 + 2 = 4$ способа.
• Нижняя «Р»: $2$ способа.

Итог для «Р»: [2, 4, 2].

Для четвертой буквы «Ш»:

• Верхняя «Ш»: $2 + 4 = 6$ способов.
• Нижняя «Ш»: $4 + 2 = 6$ способов.

Итог для «Ш»: [6, 6].

Для пятой буквы «Р»:

• Верхняя «Р»: $6$ способов.
• Средняя «Р»: $6 + 6 = 12$ способов.
• Нижняя «Р»: $6$ способов.

Итог для «Р»: [6, 12, 6].

Для шестой буквы «У»:

• Верхняя «У»: $6 + 12 = 18$ способов.
• Нижняя «У»: $12 + 6 = 18$ способов.

Итог для «У»: [18, 18].

Для седьмой буквы «Т»:

• Верхняя «Т»: $18$ способов.
• Средняя «Т»: $18 + 18 = 36$ способов.
• Нижняя «Т»: $18$ способов.

Итог для «Т»: [18, 36, 18].

Общее число способов прочитать слово «МАРШРУТ» равно сумме всех способов, которыми можно закончить слово на любой из букв «Т» в последнем столбце: $18 + 36 + 18 = 72$.

Ответ: 72