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

Решение:

Будем считать количество путей, ведущих к каждой вершине, начиная с А. Обозначим количество путей к вершине X как N(X).

N(A) = 1 (начальная точка).

N(Б) = N(A) = 1 (есть только один путь из А в Б).

N(В) = N(A) = 1 (есть только один путь из А в В).

N(Г) = N(Б) + N(В) = 1 + 1 = 2 (можно попасть в Г из Б или из В).

N(Д) = N(Г) = 2 (можно попасть в Д только из Г).

N(Ж) = N(Д) = 2 (можно попасть в Ж только из Д).

N(И) = N(В) = 1 (можно попасть в И только из В).

N(К) = N(И) + N(Д) = 1 + 2 = 3 (можно попасть в К из И или из Д).

N(Л) = N(Ж) + N(К) = 2 + 3 = 5 (можно попасть в Л из Ж или из К).

В задании указано, что пути не должны проходить через пункт Е. На нашей схеме пункта Е нет, поэтому мы считаем все возмомые пути из А в Л.

Ответ: 5.