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

Ответ: 9

Пошаговое решение:

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

   • В город Б можно попасть только одним способом из А, значит, количество путей равно 1.
   • В город Г можно попасть только одним способом из А, значит, количество путей равно 1.
   • В город Д можно попасть только одним способом из А, значит, количество путей равно 1.
   • В город Ж можно попасть из Б и Г. Значит, количество путей в Ж равно сумме путей в Б и Г: 1 + 1 = 2.
   • В город Е можно попасть из Г и Д. Значит, количество путей в Е равно сумме путей в Г и Д: 1 + 1 = 2.
   • В город К можно попасть из Б и Ж. Значит, количество путей в К равно сумме путей в Б и Ж: 1 + 2 = 3.
   • В город Л можно попасть из Ж, Е и К. Значит, количество путей в Л равно сумме путей в Ж, Е и К: 2 + 2 + 3 = 7.
   • В город М можно попасть из Л и Е. Значит, количество путей в М равно сумме путей в Л и Е: 7 + 2 = 9.
   • В город Н можно попасть из Е. Значит, количество путей в Н равно количеству путей в Е: 2.
   • В город П можно попасть из М, Л и Н. Значит, количество путей в П равно сумме путей в М, Л и Н: 9 + 7 + 2 = 18.

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

   Пути до М мы уже посчитали - их 9.

3. Определим количество путей из города М в город П:

   • В город Л можно попасть из Ж, Е и К. Но так как мы уже в М, то рассмотрим только путь из М в Л.
   • В город Н можно попасть из Е.
   • В город П можно попасть из М, Л и Н.

4. Считаем количество путей, проходящих через М:

   • A -> Б -> Ж -> Л -> M -> П
   • A -> Б -> К -> Л -> M -> П
   • A -> Г -> Ж -> Л -> M -> П
   • A -> Г -> Е -> Л -> M -> П
   • A -> Г -> Е -> H -> П
   • A -> Д -> Е -> Л -> M -> П
   • A -> Д -> Е -> H -> П
   • A -> Б -> Ж -> Л -> M -> П
   • A -> Б -> К -> Л -> M -> П

5. Считаем количество путей непосредственно из М в П: только один путь.

Ответ: 9