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

Краткое пояснение:

Пошаговое решение:

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

• А: 1 путь (начало)
• Б: 1 путь (из А)
• В: 1 путь (из А)
• Г: Пути из А в Г: А → Б → Г (1 путь) + А → В → Г (1 путь) = 2 пути.
• Д: Пути из А в Д: А → В → Д (1 путь) + А → Б → Г → Д (2 пути) = 1 + 2 = 3 пути.
• Е: Пути из А в Е: А → Г → Е (2 пути) + А → Д → Е (3 пути) = 2 + 3 = 5 путей.
• Ж: Пути из А в Ж: А → Д → Ж (3 пути) + А → Е → Ж (5 путей) = 3 + 5 = 8 путей.
• 3: Пути из А в 3: А → Г → 3 (2 пути) + А → Е → 3 (5 путей) + А → Ж → 3 (8 путей) = 2 + 5 + 8 = 15 путей.

Ответ: 15