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

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

Рис. 39

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

1. Путь состоит из 7 последовательных ячеек, буквы в которых образуют слово «МАРШРУТ».
2. Переход от одной буквы к другой возможен в любую из 8 соседних ячеек (по горизонтали, вертикали или диагонали).
3. Каждая ячейка в пути может быть использована только один раз.
4. Координата столбца при движении от буквы к букве не должна уменьшаться. То есть, если текущая ячейка находится в столбце $j$, то следующая ячейка должна быть в столбце $j$ или $j+1$.

Будем решать задачу методом динамического программирования. Обозначим через $N_k(r, c)$ количество способов составить начальную часть слова из $k$ букв, заканчивающуюся в ячейке с координатами $(r, c)$, где $r$ – номер строки, а $c$ – номер столбца. Сетка с буквами выглядит так (пустые ячейки обозначены прочерком):

(1,1)М (1,2)Р (1,3)Р (1,4)Т
(2,1)- (2,2)А (2,3)Ш (2,4)У
(3,1)М (3,2)Р (3,3)Р (3,4)Т
(4,1)- (4,2)А (4,3)Ш (4,4)У
(5,1)М (5,2)Р (5,3)Р (5,4)Т

Шаг 1: Буква М (k=1)

Начать можно с любой из трех букв «М» в первом столбце. Таким образом, для каждой из этих ячеек существует один способ начать слово.

• $N_1(1,1) = 1$
• $N_1(3,1) = 1$
• $N_1(5,1) = 1$

Шаг 2: Буква А (k=2)

В ячейку с буквой «А» можно попасть из соседних ячеек с буквой «М».
Для ячейки А(2,2) соседними являются М(1,1) и М(3,1).
$N_2(2,2) = N_1(1,1) + N_1(3,1) = 1 + 1 = 2$
Для ячейки А(4,2) соседними являются М(3,1) и М(5,1).
$N_2(4,2) = N_1(3,1) + N_1(5,1) = 1 + 1 = 2$

Шаг 3: Буква Р (k=3)

В ячейки с буквой «Р» можно попасть из соседних ячеек с буквой «А», при условии, что номер столбца не уменьшается.
$N_3(1,2) = N_2(2,2) = 2$
$N_3(3,2) = N_2(2,2) + N_2(4,2) = 2 + 2 = 4$
$N_3(5,2) = N_2(4,2) = 2$
$N_3(1,3) = N_2(2,2) = 2$
$N_3(3,3) = N_2(2,2) + N_2(4,2) = 2 + 2 = 4$
$N_3(5,3) = N_2(4,2) = 2$

Шаг 4: Буква Ш (k=4)

В ячейки с буквой «Ш» можно попасть из соседних ячеек с буквой «Р».
Для Ш(2,3) соседними являются Р(1,2), Р(3,2), Р(1,3), Р(3,3).
$N_4(2,3) = N_3(1,2) + N_3(3,2) + N_3(1,3) + N_3(3,3) = 2 + 4 + 2 + 4 = 12$
Для Ш(4,3) соседними являются Р(3,2), Р(5,2), Р(3,3), Р(5,3).
$N_4(4,3) = N_3(3,2) + N_3(5,2) + N_3(3,3) + N_3(5,3) = 4 + 2 + 4 + 2 = 12$

Шаг 5: Буква Р (k=5)

Это пятая буква слова, и она также является буквой «Р». Согласно правилу, мы не можем использовать ту же ячейку дважды. Путь выглядит как ...Р → Ш → Р... , где ячейки для первой и второй «Р» должны быть разными. Количество путей до ячейки $Р_{next}$, идущих через $Ш$, равно общему числу путей до $Ш$ минус те пути, которые пришли в $Ш$ из $Р_{next}$.
Из Ш(2,3) можно перейти в соседние Р(1,3) и Р(3,3) (т.к. номер столбца $\geq 3$).
Вклад в $N_5(1,3)$ от Ш(2,3): $N_4(2,3) - N_3(1,3) = 12 - 2 = 10$.
Вклад в $N_5(3,3)$ от Ш(2,3): $N_4(2,3) - N_3(3,3) = 12 - 4 = 8$.
Из Ш(4,3) можно перейти в соседние Р(3,3) и Р(5,3).
Вклад в $N_5(3,3)$ от Ш(4,3): $N_4(4,3) - N_3(3,3) = 12 - 4 = 8$.
Вклад в $N_5(5,3)$ от Ш(4,3): $N_4(4,3) - N_3(5,3) = 12 - 2 = 10$.
Итоговые значения для пятого шага:
$N_5(1,3) = 10$
$N_5(3,3) = 8 + 8 = 16$
$N_5(5,3) = 10$

Шаг 6: Буква У (k=6)

В ячейки с буквой «У» можно попасть из соседних ячеек с буквой «Р» (из шага 5).
Для У(2,4) соседними являются Р(1,3) и Р(3,3).
$N_6(2,4) = N_5(1,3) + N_5(3,3) = 10 + 16 = 26$
Для У(4,4) соседними являются Р(3,3) и Р(5,3).
$N_6(4,4) = N_5(3,3) + N_5(5,3) = 16 + 10 = 26$

Шаг 7: Буква Т (k=7)

В ячейки с буквой «Т» можно попасть из соседних ячеек с буквой «У».
$N_7(1,4) = N_6(2,4) = 26$
$N_7(3,4) = N_6(2,4) + N_6(4,4) = 26 + 26 = 52$
$N_7(5,4) = N_6(4,4) = 26$

Итог

Общее число способов прочитать слово «МАРШРУТ» равно сумме всех путей, заканчивающихся на букве «Т».
Всего способов = $N_7(1,4) + N_7(3,4) + N_7(5,4) = 26 + 52 + 26 = 104$.

Ответ: 104.