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

Из А в Г можно попасть двумя способами: напрямую или через В.

Посчитаем число путей от остальных городов до М, начиная с конца схемы. Из К и Л есть по одному пути. Из И — 3 пути: напрямую в М, через К или через Л. Из З — 4 пути: через И или К. Из Ж — 5 путей: через З или К.

Из Е — 5 путей, поскольку из Е ведёт дорога в Ж. Из Д — 14 путей: через Е, З или Ж. Тогда из Г — 24 пути: через Ж, Д или Е.

Всего путей из А в М через Г: \(2\cdot24=48\).

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