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

Считаем пути слева направо, складывая количества способов, ведущих в каждую вершину.

1. До А — 1 путь. До Б и Г — по 1 пути.
2. До В ведут дороги из А и Б: 1 + 1 = 2 пути.
3. До Д можно попасть из Б: 1 путь. До Е ведут дороги из В и Г: 2 + 1 = 3 пути.
4. До Ж ведут дороги из В и Е: 2 + 3 = 5 путей.
5. До И можно попасть из Ж: 5 путей. До З можно попасть из Ж и И: 5 + 5 = 10 путей.
6. В К ведут дороги из Ж, И и З: 5 + 5 + 10 = 20 путей.

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