На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город П, проходящих через город Н?
Количество путей до города П равно сумме путей в каждый из тех городов, из которых есть дорога в П. С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов, кроме тех, которые не проходят через город Н:
А = 1
Б = А = 1
Д = А = 1
Г = А + Б = 1 + 1 = 2
В = Б + Г = 1 + 2 = 3
Е = Г + Д = 2 + 1 = 3
Ж = В + Г + Е = 3 + 2 + 3 = 8
Н = Ж = 8
М = Н = 8 (так как ищем пути проходящие через город Н)
Л = М = 8
П = Л + М = 16.
Приведем другое решение.
Заметим, что путь из города А в город П обязательно должен проходить через город Ж. По условию задачи путь должен также проходить через город Н. Тогда количество путей из города А в город П, проходящих через город Н, равно произведению количества путей из города А в город Ж, количества путей из города Ж в город Н и количества путей из города Н в город П.
Найдем количество путей из города А в город Ж:
А = 1
Б = А = 1
Д = А = 1
Г = А + Б = 1 + 1 = 2
В = Б + Г = 1 + 2 = 3
Е = Г + Д = 2 + 1 = 3
Ж = В + Г + Е = 3 + 2 + 3 = 8.
Из города Ж в город Н ведет только один путь.
Найдем количество путей из города Н в город П (при этом Н - исходный пункт):
Н = 1
М = Н = 1
Л = М = 1
П = Л + Н = 2.
Тогда количество путей из города А в город П, проходящих через город Н, равно 8 · 1 · 2 = 16.
Ответ: 16.