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

Обозначим через N(X) число путей из города А до города X. По схеме дороги направлены так: А→В, А→Б, А→Г; Б→Г; Г→И, Г→Е, Г→К; В→Д, В→И, В→К; Д→К; Е→К; И→К.

1. До А можно добраться одним способом: N(А)=1.
2. В: N(В)=N(А)=1. Б: N(Б)=N(А)=1.
3. Г: N(Г)=N(А)+N(Б)=1+1=2.
4. Д: N(Д)=N(В)=1. И: N(И)=N(В)+N(Г)=1+2=3. Е: N(Е)=N(Г)=2.
5. К: N(К)=N(В)+N(Д)+N(И)+N(Г)+N(Е)=1+1+3+2+2=9.

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