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

Решение:

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

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

1. N(К) = 1 (точка назначения).
2. N(Ж) = N(К) = 1 (стрелка ведет только в К).
3. N(И) = N(К) = 1 (стрелка ведет только в К).
4. N(Е) = N(Ж) + N(И) = 1 + 1 = 2 (стрелки ведут в Ж и И).
5. N(Г) = N(Е) = 2 (стрелка ведет только в Е).
6. N(Д) = N(Г) = 2 (стрелка ведет только в Г).
7. N(А): Мы должны найти пути из А в К, не проходящие через В. Пути из А идут в Б и Г.
• Путь через Г: N(А → Г) = N(Г) = 2.
• Путь через Б: из А в Б. Из Б стрелка ведет в В и Д. Так как нам нужно избегать В, мы рассматриваем путь через Д. N(А → Б → Д) = N(Д) = 2.
8. N(А) = N(А → Г) + N(А → Б → Д) = 2 + 2 = 4.

Ответ: Существует 4 пути из города А в город К, не проходящие через пункт В.