6. Тип 9 № 10253. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город Ж?

Сначала посчитаем, сколькими способами можно добраться из А до каждой вершины, ведущей в Ж. Число способов до вершины равно сумме способов до вершин, из которых в неё ведут дороги.

• До Д — 1 способ; до Г — 2 способа (из А или через Д).
• До В — 3 способа (из А или через Г); до Б — 4 способа (из А или через В).
• До Е — 4 способа. До З — 1 + 2 + 3 = 6 способов (через Д, Г или В).
• В Ж ведут дороги из Б, В, Е и З, поэтому число путей из А в Ж: 4 + 3 + 4 + 6 = 17.

Из Ж в И ведёт одна дорога, значит каждый из этих путей продолжается до И единственным способом.

Ответ: 17 путей.