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