На рисунке — схема дорог, связывающих города А, B, C, D, E, F, G, Н. По каждой дороге можно двигаться только в одном направлении, указанной стрелкой. Сколько существует различных путей из города А в город Н?

Question

Вопрос:

На рисунке — схема дорог, связывающих города А, B, C, D, E, F, G, Н. По каждой дороге можно двигаться только в одном направлении, указанной стрелкой. Сколько существует различных путей из города А в город Н?

Фотография

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

Accepted Answer

Для решения задачи воспользуемся методом подсчета количества путей в каждый город, двигаясь от начального города A к конечному H. Обозначим количество путей в город X как $N(X)$. 1. $N(A) = 1$ (начальная точка). 2. В города B, C, D можно попасть только из A: - $N(B) = N(A) = 1$ - $N(C) = N(A) = 1$ - $N(D) = N(A) = 1$ 3. В город E можно попасть из B, C и D: - $N(E) = N(B) + N(C) + N(D) = 1 + 1 + 1 = 3$ 4. В город F можно попасть из E, C, D: - $N(F) = N(E) + N(C) + N(D) = 3 + 1 + 1 = 5$ 5. В город G можно попасть из E и F: - $N(G) = N(E) + N(F) = 3 + 5 = 8$ 6. В город H можно попасть из G и F: - $N(H) = N(G) + N(F) = 8 + 5 = 13$ Ответ: 13

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

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