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

Считаем число путей до М, исключая город Г и все дороги через него. Из К есть 1 путь в М, а из Л — 1 путь. Значит, из И — 1 путь через К; из З — 1 путь через К; из Ж — 3 пути: через К, И или З.

Из Е — 5 путей: через Ж, И или З. Из Д — 9 путей: через З, Ж или Е. Поэтому из В — 5 путей (через Е), а из Б, не заходя в Г, — \(5+9=14\) путей (через В или Д).

Из А можно отправиться в Б или В, поэтому общее число путей: \(14+5=19\).

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