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