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

Question

Вопрос:

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

Фотография

Ответ ассистента

Accepted Answer

Для решения этой задачи нужно посчитать количество путей из города А в город К, двигаясь по стрелочкам. Обозначим количество путей в каждую точку как $N$. Будем считать количество путей, приходящих в каждую вершину по очереди: 1. В город **А** ведет только один путь (начальная точка), поэтому $N(А) = 1$. 2. В город **Б** можно попасть только из А: $N(Б) = N(А) = 1$. 3. В город **Г** можно попасть только из А: $N(Г) = N(А) = 1$. 4. В город **В** можно попасть из А, Б и Г: $N(В) = N(А) + N(Б) + N(Г) = 1 + 1 + 1 = 3$. 5. В город **Д** можно попасть из Б и В: $N(Д) = N(Б) + N(В) = 1 + 3 = 4$. 6. В город **Е** можно попасть из Г и В: $N(Е) = N(Г) + N(В) = 1 + 3 = 4$. 7. В город **К** можно попасть из Д и Е: $N(К) = N(Д) + N(Е) = 4 + 4 = 8$. Ответ: 8

Ответ ассистента

Другие решения