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

Город К можно посетить только по дороге И → К, а из К ведёт дорога в М. Поэтому считаем пути из А в И.

При последовательном подсчёте числа путей до каждой вершины получаем: до Б — 1, до Г — 1, до Д — 2, до В — 3, до З — 6, до Е — 1, до Ж — 10, до И — 17. Число путей до вершины равно сумме чисел путей до всех вершин, из которых в неё ведут дороги.

Ответ: 17 путей.