На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в пункте Ж, не содержат этот пункт в качестве промежуточного и проходят через любой другой пункт не более одного раза.
Заметим, что дорогу В–Е можно не учитывать, так как она приводит к повторению пунктов прохождения. Тогда, посчитаем количество путей до каждого из городов:
Е = Ж = 1.
Д = К + Е = 1 + К.
А = Д + Е = 2 + К.
Б = А = 2 + К.
В = Б = 2 + К.
Г = Ж + В − К = 3.
И = Г = 3.
Н = И = 3.
М = Н + И = 6.
Л = М = 6.
К = Л = 6.
Заметим, что из полученных К для Д, А, Б и В подходят только 2 дороги, которые не ведут к повторам. Итого, получаем:
Д = 3.
А = 4.
В = Б = А = 4.
Итак, искомое количество путей: 6 + 6 + 6 + 4 = 22.
Ответ: 22.