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

