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

Решение:

Будем использовать метод подсчёта путей, суммируя количество путей, ведущих в каждую вершину.

1. N(A) = 1 (исходная точка).
2. N(Б) = N(A) = 1.
3. N(Г) = N(A) = 1.
4. N(Д) = N(A) + N(Г) = 1 + 1 = 2.
5. N(В) = N(A) = 1.
6. N(Ж) = N(Б) + N(В) + N(Д) = 1 + 1 + 2 = 4.
7. N(И) = N(Ж) = 4.
8. N(К) = N(И) = 4.
9. N(Л) = N(И) + N(К) = 4 + 4 = 8.

Подробный подсчет:

N(A) = 1

N(Б) = N(A) = 1

N(Г) = N(A) = 1

N(Д) = N(A) + N(Г) = 1 + 1 = 2

N(В) = N(A) = 1

N(Ж) = N(Б) + N(В) + N(Д) = 1 + 1 + 2 = 4

N(И) = N(Ж) = 4

N(К) = N(И) = 4

N(Л) = N(И) + N(К) = 4 + 4 = 8

Ответ: 8