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

Решение:

Чтобы найти количество путей из города А в город Ж, будем двигаться по схеме, считая количество путей к каждому городу:

• Из А можно попасть в Б. Путь: А → Б (1 путь).
• Из А также можно попасть в Г. Путь: А → Г (1 путь).
• Из Б можно попасть в В. Путь: А → Б → В (1 путь).
• Из Г можно попасть в В и Д.
• Путь через В: А → Г → В (1 путь).
• Путь через Д: А → Г → Д (1 путь).
• Итого к В: 1 (из А→Б→В) + 1 (из А→Г→В) = 2 пути.
• Из В можно попасть в Е. Путь: А → Б → В → Е, А → Г → В → Е (2 пути).
• Из Д можно попасть в Е и Ж.
• Путь через Е: А → Г → Д → Е (1 путь).
• Путь через Ж: А → Г → Д → Ж (1 путь).
• Итого к Е: 2 (из В) + 1 (из Д) = 3 пути.
• Из Е можно попасть в Ж. Путь: А → Б → В → Е → Ж, А → Г → В → Е → Ж, А → Г → Д → Е → Ж (3 пути).
• Также есть прямой путь из Д в Ж: А → Г → Д → Ж (1 путь).
• Всего путей из А в Ж: 3 (через Е) + 1 (прямой из Д) = 4 пути.

Ответ: 4