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