На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город П, проходящих через город М?

Для решения задачи нужно найти количество путей из города А в город П, проходящих через город М. Мы разобьем задачу на две части: найдем количество путей из А в М и из М в П, а затем перемножим результаты. ### 1. Пути из А в М Обозначим через $N(X)$ количество путей из А в город X. - $N(А) = 1$ - $N(Б) = N(А) = 1$ - $N(Г) = N(А) + N(Б) = 1 + 1 = 2$ - $N(В) = N(Б) = 1$ - $N(Д) = N(А) = 1$ - $N(Е) = N(Г) + N(Д) = 2 + 1 = 3$ - $N(Ж) = N(В) + N(Г) + N(Е) = 1 + 2 + 3 = 6$ - $N(Н) = N(Д) + N(Е) + N(Ж) = 1 + 3 + 6 = 10$ - $N(М) = N(Ж) + N(Н) = 6 + 10 = 16$ Итак, существует 16 путей из А в М. ### 2. Пути из М в П Теперь считаем пути из М в П (считаем М начальной точкой, $N(М) = 1$): - $N(М) = 1$ - $N(Л) = N(М) = 1$ - $N(К) = N(Ж) + N(Л) = 0 + 1 = 1$ (но через Ж из М нельзя попасть, в М только входят дороги из Ж и Н, а выходят в Л, Н... стоп, посмотрим на граф внимательнее). Пересчитаем пути из М: Из М выходят дороги в Л и Н. - $N(М) = 1$ - $N(Л) = N(М) = 1$ - $N(Н) = N(М) = 1$ - $N(К) = N(Л) = 1$ (из К идут дороги в Л (уже учтено) и П. Стоп, из Ж идут в К, Л. Из М в Л, Н. Из К в Л, П.) Давайте аккуратно по графу: - $N(М) = 1$ - $N(Л) = N(М) + N(К) = 1 + 0 = 1$ (так как из М идет дорога в Л, а из К в Л). - $N(Н) = N(М) = 1$ - $N(К) = N(Ж) + N(Л)$ — нет, Ж не достижима из М. Значит: - Из М можно попасть в Л и Н. - Из Л можно попасть в П. - Из Н можно попасть в Л, П. - Из К можно попасть в Л, П. Вернемся к истоку М: - $N(М) = 1$ - $N(Л) = N(М) = 1$ (путь М -> Л) - $N(Н) = N(М) = 1$ (путь М -> Н) - $N(К) = 0$ (из М в К пути нет) - $N(П) = N(Л) + N(Н) + N(К) = 1 + 1 + 0 = 2$ Итого путей из М в П: 2. ### 3. Итог Количество путей через М равно: $N(А \rightarrow М) \times N(М \rightarrow П) = 16 \times 2 = 32$. **Ответ: 32**