На рисунке — схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите, сколько существует различных путей из города А в город Л.

Решение:

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

1. A: 1 путь (начальный город).
2. Г: 1 путь (из А).
3. Д: 1 путь (из А).
4. Б: 1 путь (из А).
5. Е: 1 путь (из А).
6. В: Пути из Г и Б. Количество путей в В = Пути(Г) + Пути(Б) = 1 + 1 = 2.
7. Ж: Пути из Г и В. Количество путей в Ж = Пути(Г) + Пути(В) = 1 + 2 = 3.
8. И: Пути из Е и Ж. Количество путей в И = Пути(Е) + Пути(Ж) = 1 + 3 = 4.
9. 3: Пути из Д и В. Количество путей в 3 = Пути(Д) + Пути(В) = 1 + 2 = 3.
10. К: Пути из 3 и Ж. Количество путей в К = Пути(3) + Пути(Ж) = 3 + 3 = 6.
11. Л: Пути из Ж, И и К. Количество путей в Л = Пути(Ж) + Пути(И) + Пути(К) = 3 + 4 + 6 = 13.

Ответ: 13