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

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

1. Из города А:
   
   • В город Б: 1 путь (А → Б)
   • В город И: 1 путь (А → И)
2. Из города Б:
   
   • В город В: 1 путь (Б → В)
   • В город Д: 1 путь (Б → Д)
3. Из города В:
   
   • В город Д: 1 путь (В → Д)
   • В город К: 1 путь (В → К)
4. Из города И:
   
   • В город Г: 1 путь (И → Г)
   • В город Е: 1 путь (И → Е)
5. Из города Д:
   
   • В город К: 1 путь (Д → К)
6. Из города Г:
   
   • В город К: 1 путь (Г → К)
7. Из города Е:
   
   • В город К: 1 путь (Е → К)

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

Пути через Д:

• А → Б → Д → К: 1 путь
• А → Б → В → Д → К: 1 путь

Пути напрямую в К:

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

Общее количество путей:

Пути, ведущие в К:

• Из В: 1 (А → Б → В → К)
• Из Д: 2 (А → Б → Д → К, А → Б → В → Д → К)
• Из Г: 1 (А → И → Г → К)
• Из Е: 1 (А → И → Е → К)

Итого: 1 + 2 + 1 + 1 = 5 путей.

Давай пересчитаем более систематично, по городам, куда можно попасть из А:

Город А: 1 (сам город)

Город Б: 1 (А → Б)

Город И: 1 (А → И)

Город В: 1 (А → Б → В)

Город Д: 2 (А → Б → Д, А → Б → В → Д)

Город Г: 1 (А → И → Г)

Город Е: 1 (А → И → Е)

Город К:

К = (Пути из В) + (Пути из Д) + (Пути из Г) + (Пути из Е)

К = 1 (А → Б → В → К) + 2 (А → Б → Д → К, А → Б → В → Д → К) + 1 (А → И → Г → К) + 1 (А → И → Е → К) = 5

Ответ: 5