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

Решение:

Будем считать количество путей до каждого города, начиная с А. Количество путей до города А равно 1. Цель — найти пути через Л.

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

Ответ: 34