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

Обозначим через N(X) количество путей из города А в город X. Для каждого города складываем количества путей, ведущих в него.

1. В город А ведёт начало маршрута: N(А) = 1.
2. В Б можно попасть только из А, поэтому N(Б) = 1.
3. В В ведут дороги из А и Б: N(В) = 1 + 1 = 2.
4. В Д ведёт дорога из А: N(Д) = 1.
5. В Г ведут дороги из А, В и Д: N(Г) = 1 + 2 + 1 = 4.
6. В Е ведут дороги из Б и В: N(Е) = 1 + 2 = 3.
7. В Ж ведёт дорога из Д: N(Ж) = 1.
8. В К ведут дороги из В, Г, Е и Ж: N(К) = 2 + 4 + 3 + 1 = 10.

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