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

Решение:

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

• Из А можно попасть только в Б. Путей в Б: 1.
• Из А можно попасть только в Г. Путей в Г: 1.
• Из Б можно попасть в В. Путей в В (через Б): 1.
• Из Г можно попасть в В. Путей в В (через Г): 1.
• Итого путей в В: 1 + 1 = 2.
• Из В можно попасть в Д. Путей в Д (через В): 2.
• Из Г можно попасть в Д. Путей в Д (через Г): 1.
• Итого путей в Д: 2 + 1 = 3.
• Из Д можно попасть в К. Путей в К (через Д): 3.
• Из В можно попасть в К. Путей в К (через В): 2.
• Из Г можно попасть в К. Путей в К (через Г): 1.
• Итого путей в К: 3 + 2 + 1 = 6.

Ответ: 6