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