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

Задание 3. Количество путей через город Г

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

Начнем с города А:

• А: 1 путь (начало).

Двигаемся по стрелкам:

• Б: 1 путь (из А).
• В: 1 путь (из А).
• Г: Путь может прийти из А или из В. Поскольку нам нужен путь через Г, нас интересуют пути, которые В НЕ ПОСЕТИЛИ. Поэтому рассматриваем только путь из А. Количество путей в Г из А: 1 (через А→Г).
• Д: Путь может прийти из А или из Г. Количество путей в Д из А: 1 (А→Д). Количество путей в Д из Г: 1 (А→Г→Д). Итого: 1 + 1 = 2 пути.
• Е: Путь может прийти из А или из В. Количество путей в Е из А: 1 (А→Е). Количество путей в Е из В: 1 (А→Б→В→Е). Итого: 1 + 1 = 2 пути.
• Ж: Путь может прийти из А, Г, Д. Количество путей в Ж из А: 1 (А→Г→Ж). Количество путей в Ж из Д: 2 (А→Д→Ж, А→Г→Д→Ж). Итого: 1 + 2 = 3 пути.
• З: Путь может прийти из Е. Количество путей в З из Е: 2 (А→Е→З, А→Б→В→Е→З).
• И: Путь может прийти из Е. Количество путей в И из Е: 2 (А→Е→И, А→Б→В→Е→И).
• К: Путь может прийти из Ж. Количество путей в К из Ж: 3 (А→Г→Ж→К, А→Д→Ж→К, А→Г→Д→Ж→К).
• Л: Путь может прийти из Г, Ж, И, К.

Нам нужны пути, проходящие через Г. Следовательно, мы должны посчитать пути, которые начинаются с A → Г.

Количество путей из A в Г = 1 (A → Г).

Количество путей из Г в Л:

• Из Г можно попасть в Ж (1 путь) и Д (1 путь).
• Пути через Г:
• A → Г → Ж → К → Л: 1 * 1 * 1 * 1 = 1 путь.
• A → Г → Д → Ж → К → Л: 1 * 1 * 1 * 1 * 1 = 1 путь.
• A → Г → И → Л: 1 * 1 = 1 путь. (Из Г нет прямого пути в И, только через Е, а нам нужно через Г)

Давайте пересчитаем, учитывая все пути:

• А: 1
• Б: 1
• В: 1
• Г: 1 (из А)
• Д: 1 (из А) + 1 (из Г) = 2
• Е: 1 (из А) + 1 (из В) = 2
• Ж: 1 (из Г) + 2 (из Д) = 3
• З: 2 (из Е)
• И: 2 (из Е)
• К: 3 (из Ж)
• Л: 1 (из Г) + 3 (из Ж) + 2 (из И) + 3 (из К) = 9

Нас интересуют пути, проходящие через Г. Это пути, где Г является промежуточной вершиной.

Пути, проходящие через Г:

1. А → Г → Л: 1 * 1 = 1 путь.
2. А → Г → Д → Ж → К → Л: 1 * 1 * 1 * 1 * 1 = 1 путь.
3. А → Г → Ж → К → Л: 1 * 1 * 1 = 1 путь.

Теперь учтем, что из А можно попасть в Г несколькими способами:

• A → Г: 1 путь.

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

• Л (прямо): 1 путь.
• Ж: 1 путь.
• Д: 1 путь.

Если мы идем из А в Г, то далее из Г:

• A → Г → Л: 1 * 1 = 1 путь.
• A → Г → Ж → К → Л: 1 * 1 * 1 = 1 путь.
• A → Г → Д → Ж → К → Л: 1 * 1 * 1 * 1 = 1 путь.

Это все пути, которые ОБЯЗАТЕЛЬНО проходят через Г. Таким образом, всего 3 таких пути.

Ответ: 3.