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

Привет! Давай разберёмся, сколько есть путей из города А в город П через город Н.

Метод решения: Будем считать количество путей до каждого города, двигаясь от города А. Это называется методом динамического программирования или просто подсчётом путей.

Шаг 1: Подсчет путей до каждого города, начиная с А.

• А: 1 путь (мы находимся в нём).
• Б: 1 путь (из А).
• Г: 1 путь (из А).
• В: 1 путь (из Б).
• Д: 1 путь (из Г).
• Е: Пути из Б и Г. Количество путей до Е = (пути до Б) + (пути до Г) = 1 + 1 = 2.
• Ж: Пути из В и Е. Количество путей до Ж = (пути до В) + (пути до Е) = 1 + 2 = 3.
• К: Пути из Ж. Количество путей до К = (пути до Ж) = 3.
• Л: Пути из К. Количество путей до Л = (пути до К) = 3.
• М: Пути из Ж. Количество путей до М = (пути до Ж) = 3.
• Н: Пути из Е и М. Количество путей до Н = (пути до Е) + (пути до М) = 2 + 3 = 5.
• П: Пути из Л и Н. Количество путей до П = (пути до Л) + (пути до Н) = 3 + 5 = 8.

Важно: Нас интересуют пути, проходящие через город Н. Мы уже посчитали, что из города А в город Н ведет 5 путей.

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

• Из Н стрелки ведут только в П.

Значит, количество путей из Н в П равно количеству путей, которые пришли в Н, умноженному на количество выходов из Н, ведущих в П. Так как из Н ведет только одна стрелка в П, это количество равно 1.

Итоговый подсчет:

• Путей из А в Н: 5
• Путей из Н в П: 1
• Общее количество путей из А в П через Н = (Пути из А в Н) * (Пути из Н в П) = 5 * 1 = 5.

Ответ: 5