На рисунке – схема дорог, связывающих города A, Б, В, Г, Д, Е и K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K?
Решение:
Будем считать количество путей динамически, слева направо, начиная с города A.
Обозначим P(X) – число различных путей из A в город X.
- Начальная точка: P(A) = 1.
- Из A можно попасть в Б, В и Г, значит:
- P(Б) = P(A) = 1;
- P(В) = P(A) + P(Б) (из A напрямую и через Б) ⇒ P(В) = 1 + 1 = 2;
- P(Г) = P(A) = 1.
- Далее:
- В Д ведут дороги из Б и В: P(Д) = P(Б) + P(В) = 1 + 2 = 3;
- В Е ведут дороги из В и Г: P(Е) = P(В) + P(Г) = 2 + 1 = 3.
- В город K можно попасть из Д, В и Е, значит:
- P(K) = P(Д) + P(В) + P(Е) = 3 + 2 + 3 = 8.
Следовательно, из города A в город K существует 8 различных путей.
Ответ: 8
