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

Решение:

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

Из А в Б: 1 путь.

Из А в Г: 1 путь.

Из А в Д: 1 путь.

Из Б в Ж: 1 путь.

Из Г в Ж: 1 путь.

Из Г в Е: 1 путь.

Из Д в Ж: 1 путь.

Путей в Ж из А: 1 (А→Б→Ж) + 1 (А→Г→Ж) + 1 (А→Д→Ж) = 3 пути.

Из Ж в К: 1 путь.

Из Ж в Е: 1 путь.

Из К в Л: 1 путь.

Из К в М: 1 путь.

Из Е в Л: 1 путь.

Из Е в М: 1 путь.

Путей в Л из А через Ж: 3 (А→...→Ж→К→Л) + 3 (А→...→Ж→Е→Л) = 6 путей.

Путей в М из А через Ж: 3 (А→...→Ж→К→М) + 3 (А→...→Ж→Е→М) = 6 путей.

Из Л в П: 1 путь.

Из М в П: 1 путь.

Путей в П из А через М: 6 (А→...→М→П) = 6 путей.

Ответ: 6