5. На рисунке — схема дорог, связывающих города А, В, С, D, E, G, Н, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город D?

Решение:

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

• А: 1 путь (начальная точка)
• G: 1 путь (из А)
• B: 1 путь (из А)
• E: Количество путей в E равно сумме путей в города, из которых в E ведут стрелки (A, B, G, C, F).
• Пути в E: Из А в E (1 путь), из G в E (1 путь), из B в E (1 путь). Итого в E: 1 + 1 + 1 = 3 пути.
• C: 1 путь (из B)
• F: 1 путь (из E)
• D: Количество путей в D равно сумме путей в города, из которых в D ведут стрелки (C, E, F).
• Пути в D: Из C в D (1 путь), из E в D (3 пути), из F в D (1 путь). Итого в D: 1 + 3 + 1 = 5 путей.

Ответ: 5