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

Решение:

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

1. Город А: Из города А можно попасть только в Б и Г. Обозначим количество путей из А в А как 1 (начальная точка).

2. Город Б: Из А в Б — 1 путь.

3. Город Г: Из А в Г — 1 путь.

4. Город В: Можно попасть из Б. Количество путей в В = количество путей в Б = 1.

5. Город Д: Можно попасть из Б. Количество путей в Д = количество путей в Б = 1.

6. Город Е: Можно попасть из В и Г. Количество путей в Е = количество путей в В + количество путей в Г = 1 + 1 = 2.

7. Город Ж: Можно попасть из Д и Е. Количество путей в Ж = количество путей в Д + количество путей в Е = 1 + 2 = 3.

8. Город З: Можно попасть из В, Ж и А. Количество путей в З = количество путей в В + количество путей в Ж + количество путей из А в З (если бы такая дорога была напрямую). Но мы должны идти из А. В З можно попасть из В (1 путь), из Ж (3 пути) и из А (1 путь). Но дорога из А в З не существует. Рассмотрим пути, ведущие ТОЛЬКО в З:

Путь А → Б → В → З (1 путь)

Путь А → Б → Д → Ж → З (1 путь)

Путь А → Г → Е → Ж → З (1 путь)

Путь А → Г → Е → В → З (1 путь)

Пересчитаем по узлам:

A: 1 путь (сам себя)

Б: 1 путь (из А)

Г: 1 путь (из А)

В: 1 путь (из Б)

Д: 1 путь (из Б)

Е: 2 пути (из В + из Г = 1+1)

Ж: 3 пути (из Д + из Е = 1 + 2)

З: 4 пути (из В + из Ж = 1 + 3)

Давайте проверим все возможные пути из А в З:

1. А → Б → В → З

2. А → Б → Д → Ж → З

3. А → Г → Е → В → З

4. А → Г → Е → Ж → З

Всего 4 пути.

Ответ: 4