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