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

Решение:

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

1. Из А: В город А прибывает 0 путей. Из города А можно двигаться в города B и E.
2. В B: Есть 1 путь из А в B (A → B).
3. В E: Есть 1 путь из А в E (A → E).
4. В C: Из B в C идет 1 путь (A → B → C).
5. В F: Из E в F идет 1 путь (A → E → F).
6. В G: Из E в G идет 1 путь (A → E → G).
7. В D:
   1. Из C в D идет 1 путь (A → B → C → D).
   2. Из E в D идет 1 путь (A → E → D).
   3. Из G в D идет 1 путь (A → E → G → D).

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

Пути в D:

• Из C: 1 путь (A → B → C → D)
• Из E: 1 путь (A → E → D)
• Из G: 1 путь (A → E → G → D)

Общее количество путей из А в D = 1 (из C) + 1 (из E) + 1 (из G) = 3.

Ответ: 3