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

Решение:

Для решения этой задачи будем использовать метод подсчета количества путей, исходящих из начальной точки (А), и суммирования путей в конечную точку (К).

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

• N(А) = 1 (исходная точка)
• N(Б) = N(А) = 1 (только из А)
• N(Г) = N(А) = 1 (только из А)
• N(В) = N(Б) = 1 (только из Б)
• N(Д) = N(Б) + N(Г) = 1 + 1 = 2 (из Б и из Г)
• N(Е) = N(В) + N(Д) = 1 + 2 = 3 (из В и из Д)
• N(К) = N(Д) + N(Е) = 2 + 3 = 5 (из Д и из Е)

Ответ: 5