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

Считаем пути, последовательно суммируя количества для всех дорог, ведущих в город.

1. В A — 1 путь. В B, C и D ведут дороги непосредственно из A, поэтому в каждом из этих городов — по 1 пути.
2. В E ведут дороги из A и D: 1 + 1 = 2.
3. В F ведёт дорога из E, поэтому в F — 2 пути.
4. В G ведут дороги из C, D, E и F: 1 + 1 + 2 + 2 = 6.
5. В H ведут дороги из B, F и G: 1 + 2 + 6 = 9.

Ответ: 9 путей.