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

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

1. Из А начинаются пути: N(А) = 1.
2. В Б и Г ведут дороги из А: N(Б) = 1, N(Г) = 1.
3. В Д ведёт дорога из Б: N(Д) = 1.
4. В Е ведёт дорога из Г: N(Е) = 1.
5. В В ведут дороги из Б и Г: N(В) = 1 + 1 = 2.
6. В К ведут дороги из Б, Д, В, Г и Е: N(К) = 1 + 1 + 2 + 1 + 1 = 6.

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