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

Решение:

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

1. Из А можно попасть в Б, В, Г.
2. Из Б можно попасть в Е.
3. Из В можно попасть в Е, Ж.
4. Из Г можно попасть в Е, Ж, К.
5. Из Е можно попасть в К.
6. Из Ж можно попасть в К.

Рассмотрим пути:

• А → Б → Е → К
• А → В → Е → К
• А → В → Ж → К
• А → Г → Е → К
• А → Г → Ж → К
• А → Г → К

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

Ответ: 6