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

Решение:

Решим задачу, подсчитав количество путей до каждого города, начиная с города А.

1. А: Из города А можно попасть только в А (начальная точка). Количество путей = 1.
2. Б: Из А можно попасть в Б. Количество путей до Б = 1.
3. В: Из А можно попасть в В. Количество путей до В = 1.
4. Г: Из В можно попасть в Г. Количество путей до Г = 1 (А → В → Г).
5. Д: Из Б можно попасть в Д. Количество путей до Д = 1 (А → Б → Д).
6. Е: Из Г можно попасть в Е. Количество путей до Е = 1 (А → В → Г → Е).
7. К: В К можно попасть из В, Д, Е.
• Из В: 1 путь (А → В → К).
• Из Д: 1 путь (А → Б → Д → К).
• Из Е: 1 путь (А → В → Г → Е → К).
8. Всего путей до К: 1 + 1 + 1 = 3.

Ответ: 3.