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

Решение:

Будем считать количество путей, ведущих в каждый город, начиная с города А.

• А: 1 путь.
• F: 1 путь (A → F).
• B: 1 путь (A → F → B).
• E: 1 путь (A → F → E).
• C: Путь в C может быть из B (A → F → B → C) или из E (A → F → E → C). Всего 1 + 1 = 2 пути.
• D: Путь в D может быть из C (A → F → B → C → D или A → F → E → C → D) или из B (A → F → B → D).
• Пути из C в D: 2 пути (из C ведет одна дорога в D).
• Пути из B в D: 1 путь (из B ведет одна дорога в D).
• Общее количество путей из А в D = (пути через C) + (пути через B) = 2 + 1 = 3 пути.

Ответ: 3.