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

Решение:

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

1. Из города А:
• В город А: 1 путь (начало).
• В город G: 1 путь (А → G).
• В город E: 1 путь (А → E).
• В город B: 1 путь (А → B).
2. В город H:
• Из города G: 1 путь (А → G → H).
3. В город F:
• Из города E: 1 путь (А → E → F).
4. В город C:
• Из города B: 1 путь (А → B → C).
5. В город D:
• Из города H: 1 путь (А → G → H → D).
• Из города F: 1 путь (А → E → F → D).
• Из города C: 1 путь (А → B → C → D).

Сложим количество путей, ведущих в город D:

1 (из H) + 1 (из F) + 1 (из C) = 3 пути.

Ответ: 3