На рисунке — схема дорог, которые связывают города А, Б, В, Г, Д, Е, Ж и К.

Question

Реши задание на изображении

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

[Рисунок: направленный граф. Города расположены: А — сверху; ниже Б — слева, В — в центре, Ж — справа; ниже Г — в центре-слева; Е — внизу слева; Д — в самом низу; К — внизу справа. Стрелки: А→Б, А→В, А→Ж; Б→В, Б→Г, Б→Е; Ж→В, Ж→К; В→Г, В→К; Г→Е, Г→К; Е→Д; Д→К.]

Answer

Правильный ответ: 13 путей. Значение 8 не подходит: при таком подсчёте теряются некоторые маршруты через Г и Е.

Пусть $N(X)$ — число путей из А в город $X$. Тогда число путей в город равно сумме путей из всех городов, откуда в него ведёт стрелка:

$$
N(X)=\sum_{Y\to X} N(Y).
$$

Начальное значение: $N(A)=1$ — один «пустой» путь, то есть мы ещё не вышли из А.

По стрелкам на схеме считаем по порядку:

$N(Б)=1$ — из А;

$N(Ж)=1$ — из А;

$N(В)=N(A)+N(Б)+N(Ж)=1+1+1=3$;

$N(Г)=N(Б)+N(В)=1+3=4$;

$N(Е)=N(Б)+N(Г)=1+4=5$;

$N(Д)=N(Е)=5$;

в К ведут стрелки из В, Г, Ж и Д, поэтому

$$
N(К)=N(В)+N(Г)+N(Ж)+N(Д)=3+4+1+5=13.
$$

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