№4. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Решение:

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

1. Из города А можно попасть только в город Б. Путей в Б: 1.
2. Из города А можно попасть в город В. Путей в В: 1.
3. В город Г можно попасть из А и из Б. Путей в Г = (пути в А) + (пути в Б) = 1 + 1 = 2.
4. В город Д можно попасть из Г. Путей в Д = (пути в Г) = 2.
5. В город Е можно попасть из В и из Г. Путей в Е = (пути в В) + (пути в Г) = 1 + 2 = 3.
6. В город Ж можно попасть из Д и из Е. Путей в Ж = (пути в Д) + (пути в Е) = 2 + 3 = 5.

Ответ: 5