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

Поскольку в город М ведут только дороги из К и Л, а пути через К запрещены, каждый подходящий маршрут должен пройти через Л. По схеме из Ж можно попасть к И и затем к Л; к Л ведёт также дорога из З.

Подсчитаем количество путей из А в Ж. Из А в В можно попасть напрямую или через Б — 2 пути. В Ж ведут дороги из В и З, а в З можно попасть из В напрямую либо через Г или Д. Из В в З есть 1 путь; из А через Г — 1, через Д — 1. Итого в З из А ведут 3 пути, а в Ж через З — 3 пути. Кроме того, из В есть прямая дорога в Ж, что даёт ещё 2 пути. Всего до Ж: 3 + 2 = 5 путей.

После Ж маршрут продолжается в И, затем выбирается одна из двух дорог: в Л или в З. Путь через З затем ведёт в И повторно, что не образует пути без повторения города; поэтому учитываем только переход И → Л → М. Значит, каждый из 5 путей до Ж даёт один подходящий маршрут.

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