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

Решение:

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

1. Город А: Из города А можно попасть в города Б, В и Г. Количество путей в А равно 1 (сам город).

2. Город Б: Единственный путь в Б — из А. Количество путей: 1.
3. Город В: Пути в В: А → В. Количество путей: 1.
4. Город Г: Пути в Г: А → Г. Количество путей: 1.
5. Город Д: Пути в Д: А → Г → Д. Количество путей: 1.
6. Город Е: Путь в Е: А → Б → Е. Количество путей: 1.
7. Город Ж: Пути в Ж: А → В → Ж. Количество путей: 1.
8. Город З: Пути в З: А → В → З. Количество путей: 1.
9. Город И: Пути в И: А → Г → Д → И. Количество путей: 1.
10. Город К: Пути в К:
    • А → Б → Е → К
    • А → В → Ж → К
    • А → В → З → К
    • А → Г → Д → И → К

Подсчитаем общее количество путей:

• Из А в Б: 1
• Из А в В: 1
• Из А в Г: 1
• Из Б в Е: 1 (Всего А → Б → Е: 1)
• Из В в Ж: 1 (Всего А → В → Ж: 1)
• Из В в З: 1 (Всего А → В → З: 1)
• Из Г в Д: 1 (Всего А → Г → Д: 1)
• Из Д в И: 1 (Всего А → Г → Д → И: 1)
• Из Е в К: 1 (Всего А → Б → Е → К: 1)
• Из Ж в К: 1 (Всего А → В → Ж → К: 1)
• Из З в К: 1 (Всего А → В → З → К: 1)
• Из И в К: 1 (Всего А → Г → Д → И → К: 1)

Теперь сложим все пути, ведущие в город К:

• А → Б → Е → К: 1 путь
• А → В → Ж → К: 1 путь
• А → В → З → К: 1 путь
• А → Г → Д → И → К: 1 путь

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

Пути в К = (пути через Е) + (пути через Ж) + (пути через З) + (пути через И)

Пути в К = 1 (из Е) + 1 (из Ж) + 1 (из З) + 1 (из И) = 4

Однако, нужно пересчитать более систематически, учитывая все возможные комбинации.

Давайте определим количество путей до каждого города:

• N(A) = 1
• N(Б) = N(A) = 1
• N(В) = N(A) = 1
• N(Г) = N(A) = 1
• N(Д) = N(Г) = 1
• N(Е) = N(Б) = 1
• N(Ж) = N(В) = 1
• N(З) = N(В) = 1
• N(И) = N(Д) = 1
• N(К) = N(Е) + N(Ж) + N(З) + N(И)
• N(К) = 1 + 1 + 1 + 1 = 4

Проверим еще раз, внимательно следуя стрелкам:

Пути из А:

1. A → Б → Е → K
2. A → В → Ж → K
3. A → В → З → K
4. A → Г → Д → И → K

Всего 4 пути.

Определение количества путей до каждой вершины:

A: 1

Б: 1 (из A)

В: 1 (из A)

Г: 1 (из A)

Д: 1 (из Г)

Е: 1 (из Б)

Ж: 1 (из В)

З: 1 (из В)

И: 1 (из Д)

К: Количество путей в К = (количество путей в Е) + (количество путей в Ж) + (количество путей в З) + (количество путей в И)

К: 1 + 1 + 1 + 1 = 4