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

Решение:

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

Подсчёт путей:

1. А: 1 путь (начало).
2. Д: 1 путь (из А).
3. Б: 1 путь (из А).
4. Г: Пути из А и Д. 1 (из А) + 1 (из Д) = 2 пути.
5. Е: Пути из Г. 2 пути.
6. Ж: Пути из Б и Г. 1 (из Б) + 2 (из Г) = 3 пути.
7. В: Пути из Б и Ж. 1 (из Б) + 3 (из Ж) = 4 пути.
8. К: Пути из Ж. 3 пути.
9. Л: Пути из К. 3 пути.
10. М: Пути из Ж, К, Л. 3 (из Ж) + 3 (из К) + 3 (из Л) = 9 путей.
11. Н: Пути из М. 9 путей.
12. П: Пути из Л и Н. 3 (из Л) + 9 (из Н) = 12 путей.

Задача требует найти количество путей из города А в город П, проходящих через город Л. Путь из А в Л состоит из 3 путей. Путь из Л в П состоит из 3 путей. Следовательно, общее количество путей из А в П через Л равно произведению количества путей до Л и количества путей из Л до П.

Количество путей из А в Л: 3.

Количество путей из Л в П: 3.

Общее количество путей из А в П через Л: $$3 \times 3 = 9$$.

Ответ: 9