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

Решение:

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

• A: 1 путь (сам город).
• B: 1 путь (из A в B).
• C: 1 путь (из A в C).
• D: 1 путь (из A в D).
• E: Пути в E: из A в E (1). Итого: 1 путь.
• G: Пути в G: из B в G (1), из C в G (1). Итого: 1 + 1 = 2 пути.
• H: Пути в H: из D в H (1), из E в H (1). Итого: 1 + 1 = 2 пути.
• F: Пути в F: из G в F (2), из H в F (2). Итого: 2 + 2 = 4 пути.

Таким образом, существует 4 различных пути из города А в город F.

Ответ: 4