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

До Б можно добраться 1 способом. До Г ведут дороги непосредственно из А и из Б, поэтому способов 1 + 1 = 2. До В — 1 способ. До Д ведут дороги из Б, В и Г: 1 + 1 + 2 = 4.

Из Д до Е, З и К ведут отдельные дороги, поэтому до Е и З — по 4 пути, и ещё 4 пути приходят в К напрямую из Д. Через Е можно попасть в К напрямую или через Ж: это 4 + 4 = 8 путей. Через З — ещё 4 пути.

Итого: 4 + 8 + 4 = 16.

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