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

Считаем количество путей до каждого города, складывая количества путей из городов, откуда в него ведут дороги.

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

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