9. На рисунке — схема дорог, связывающих города А, В, С, D, E, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город G?

Решение:

Для решения задачи будем использовать метод подсчета количества путей, исходя из количества путей, ведущих в предыдущие города.

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

• N(A) = 1 (начальная точка)
• N(B) = N(A) = 1
• N(C) = N(A) = 1
• N(D) = N(B) + N(A) = 1 + 1 = 2
• N(E) = N(C) + N(B) = 1 + 1 = 2
• N(G) = N(D) + N(E) = 2 + 2 = 4

Таким образом, из города А в город G существует 4 различных пути.

Ответ: 4