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

1-й способ решения:

Начнем считать количество путей с конца маршрута с города К. NK количество различных путей из города А в город K, N общее число путей.

N_K=N_E+N_B+N_Г+N_Ж

N_Е=N_Б=N_А=1

N_В=N_Б+N_А=2

N_Г=N_В+N_А+N_Д=4

N_Ж=N_Д+N_Г=1+4=5

Подставляем значения в формулу N_K=1+2+4+5=12

2-й вариант решения:

Рассмотрим более эффективный способ...