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

Решение:

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

Начнем с города А. Количество путей из А в А равно 1.

• А: 1
• Б: из А в Б, 1 путь.
• В: из А в В, 1 путь.
• Г: из А в Г, 1 путь.
• Д: из Б в Д (1 путь) + из В в Д (1 путь) = 2 пути.
• Е: из Г в Е (1 путь) + из Д в Е (2 пути) = 3 пути.
• Ж: из Д в Ж (2 пути) + из Е в Ж (3 пути) = 5 путей.
• З: из В в З (1 путь) + из Д в З (2 пути) = 3 пути.
• И: из Е в И (3 пути) + из Ж в И (5 путей) = 8 путей.
• К: из З в К (3 пути) + из И в К (8 путей) = 11 путей.
• Л: из Ж в Л (5 путей) + из К в Л (11 путей) = 16 путей.

Теперь посчитаем количество путей из А в Л, проходящих через город 3.

Сначала найдем количество путей из А в 3:

• А: 1
• Б: 1
• В: 1
• Г: 1
• Д: 1 (из Б) + 1 (из В) = 2
• Е: 1 (из Г) + 2 (из Д) = 3
• З: 1 (из В) + 2 (из Д) = 3 пути.

Теперь найдем количество путей из 3 в Л:

• 3: 1 (точка старта для этого этапа)
• И: из 3 в И, 3 пути.
• К: из 3 в К (3 пути) + из И в К (3 пути) = 6 путей.
• Л: из И в Л (3 пути) + из К в Л (6 путей) = 9 путей.

Чтобы найти общее количество путей из А в Л через 3, умножим количество путей из А в 3 на количество путей из 3 в Л:

Количество путей = (Пути из А в 3) * (Пути из 3 в Л)

Количество путей = 3 * 9 = 27.

Ответ: 27