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

Считаем пути динамически: число способов добраться до каждой вершины равно сумме способов добраться до всех вершин, из которых в неё ведут стрелки.

По схеме направленные дороги: А→Б, А→В, А→Г; Б→В и Б→Д; Г→В и Г→Е; В→Д и В→Ж; Д→И и Д→Ж; Е→Ж и Е→К; И→К; Ж→К.

1. Из А: 1 способ. Поэтому до Б и Г — по 1 способу.
2. До В можно попасть из А, Б и Г: 1 + 1 + 1 = 3 способа.
3. До Д можно попасть из Б и В: 1 + 3 = 4 способа.
4. До Е можно попасть только из Г: 1 способ.
5. До И можно попасть только из Д: 4 способа.
6. До Ж можно попасть из В, Д и Е: 3 + 4 + 1 = 8 способов.
7. До К можно попасть из И, Ж и Е: 4 + 8 + 1 = 13 способов.

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