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

Решение:

Нам нужно найти количество путей из А в М, проходящих через Ж, но не через К. Сначала посчитаем количество путей из А в Ж, а затем из Ж в М, исключив пути через К.

Пути из А в Ж:

• А → Б → Ж: 1 путь
• А → В → Ж: 1 путь
• А → Г → Ж: 1 путь
• Всего путей из А в Ж: 1 + 1 + 1 = 3.

Пути из Ж в М (не через К):

• Ж → И → Л → М: 1 путь
• Ж → И → М: 1 путь
• Ж → Д → Л → М: 1 путь
• Ж → Д → М: 1 путь
• Всего путей из Ж в М (не через К): 1 + 1 + 1 + 1 = 4.

Общее количество путей из А в М через Ж (не через К) равно произведению количества путей из А в Ж и количества путей из Ж в М (не через К):

3 пути (А → Ж) * 4 пути (Ж → М) = 12 путей.

Ответ: 12