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

Решение:

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

1. Город А:

N(А) = 1 (мы начинаем в городе А).

2. Город Б:

Из А в Б ведет одна дорога. N(Б) = N(А) = 1.

3. Город Г:

Из А в Г ведет одна дорога. N(Г) = N(А) = 1.

4. Город В:

В В можно попасть из А и из Б. N(В) = N(А) + N(Б) = 1 + 1 = 2.

5. Город Д:

В Д можно попасть из Г. N(Д) = N(Г) = 1.

6. Город Е:

В Е можно попасть из Б. N(Е) = N(Б) = 1.

7. Город Ж:

В Ж можно попасть из Г и из Д. N(Ж) = N(Г) + N(Д) = 1 + 1 = 2.

8. Город К:

В К можно попасть из В, из Е и из Ж. N(К) = N(В) + N(Е) + N(Ж) = 2 + 1 + 2 = 5.

Таким образом, существует 5 различных путей из города А в город К.

Ответ: 5