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

Сначала считаем пути из А в Г: напрямую, через Б и через В. Получаем 3 пути.

Из Г в К есть 12 путей. Их можно сгруппировать по первому переходу:

• через Д — 4 пути: Д→И→К; Д→Ж→К; Д→Ж→И→К; Д→Ж→З→К;
• через Е — 8 путей: через Д — 4 пути, через Ж — 3 пути, через З — 1 путь.

Каждый путь из А в Г можно сочетать с каждым путём из Г в К: 3 · 12 = 36.

Ответ: 36.