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

Обозначим число путей из А до каждого города. Суммируем числа путей, приходящих в город по входящим дорогам.

1. До Б и Д ведёт по одному пути: по 1.
2. До Г можно добраться из А или Д: 1 + 1 = 2.
3. До В можно попасть из А, Б или Г: 1 + 1 + 2 = 4.
4. До Е: 1 + 4 = 5; до З: 4 + 2 + 1 = 7.
5. До Ж можно добраться из Е, В или З: 5 + 4 + 7 = 16.

Из Ж путь к М, не проходящий через К, единственный: Ж → И → Л → М.

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