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

Сначала посчитаем пути из А в Г. Это пути А → Г, А → Б → В → Г и А → Д → Г — всего 3.

Из Г в Л можно добраться двумя способами: сначала через З или сначала через Ж.

• Через З: З → Л; З → И → Л; З → Е → И → Л; З → К → Л. Всего 4 пути.
• Через Ж: Ж → К → Л или Ж → З, после чего есть 4 пути до Л. Всего 5 путей.

Значит, из Г в Л ведут 4 + 5 = 9 путей. Каждый из 3 путей из А в Г можно соединить с каждым из 9 путей из Г в Л: 3 · 9 = 27.

Ответ: 27 путей.