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

Решение:

Для решения задачи будем использовать метод подсчёта количества путей, ведущих в каждый город, начиная с города А.

\( A = 1 \)

Города, в которые можно попасть напрямую из А:

\( Б = 1 \)

\( Г = 1 \)

\( Д = 1 \)

Из Б можно попасть в В и Ж:

\( В = Б = 1 \)

\( Ж = Б = 1 \)

Из Г можно попасть в В и Е:

\( В = В + Г = 1 + 1 = 2 \)

\( Е = Г = 1 \)

Из Д можно попасть в З:

\( З = Д = 1 \)

Из В можно попасть в Ж и И:

\( Ж = Ж + В = 1 + 2 = 3 \)

\( И = В = 2 \)

Из Е можно попасть в Ж и И:

\( Ж = Ж + Е = 3 + 1 = 4 \)

\( И = И + Е = 2 + 1 = 3 \)

Из З можно попасть в И и Л:

\( И = И + З = 3 + 1 = 4 \)

\( Л = З = 1 \)

Из Ж можно попасть в И и К:

\( И = И + Ж = 4 + 4 = 8 \)

\( К = Ж = 4 \)

Из И можно попасть в К и Л:

\( К = К + И = 4 + 8 = 12 \)

\( Л = Л + И = 1 + 8 = 9 \)

Из К можно попасть в М:

\( М = К = 12 \)

Из Л можно попасть в М:

\( М = М + Л = 12 + 9 = 21 \)

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

Количество путей из А в Л равно \( Л = 9 \).

Теперь посчитаем пути из Л в М:

Из Л можно попасть только в М.

\( М \text{ (из Л)} = Л = 9 \)

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

\( 9 \times 9 = 81 \)

Ответ: 81