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

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

1. В A — 1 путь; в B и C — по 1.
2. В E ведут дороги из A и C: 1 + 1 = 2.
3. В D ведут дороги из C и E: 1 + 2 = 3.
4. В G ведёт дорога из B, значит, в G — 1 путь. В F ведут дороги из A, B, E и G: 1 + 1 + 2 + 1 = 5.
5. В H ведут дороги из F и G: 5 + 1 = 6.
6. В I ведут дороги из E, F и H: 2 + 5 + 6 = 13.
7. В J ведут дороги из D, E и I: 3 + 2 + 13 = 18.

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