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

Решение:

Для решения задачи используем метод подсчета количества путей, исходящих из начальной точки.

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

Начинаем с города А:

• N(А) = 1 (исходная точка)

Теперь посчитаем количество путей до каждого следующего города, учитывая направление стрелок:

• N(Б) = N(А) = 1 (есть путь А → Б)
• N(В) = N(А) = 1 (есть путь А → В)
• N(Г) = N(А) = 1 (есть путь А → Г)
• N(Д) = N(Б) + N(В) = 1 + 1 = 2 (пути А → Б → Д и А → В → Д)
• N(Е) = N(Б) + N(Г) = 1 + 1 = 2 (пути А → Б → Е и А → Г → Е)
• N(К) = N(Д) + N(Е) = 2 + 2 = 4 (пути А → Б → Д → К, А → В → Д → К, А → Б → Е → К, А → Г → Е → К)

Таким образом, существует 4 различных пути из города А в город К.

Ответ: 4