(№ 1272) На рисунке схема дорог, связывающих города А, В, С, D, E, F, G, H, I и Ј. Но каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ј, не проходящих через город F?

Для решения этой задачи будем использовать метод подсчета путей, начиная от города А.

Обозначим количество путей из города А в каждый последующий город как N(Город).

N(A) = 1

N(B) = N(A) = 1

N(C) = N(A) = 1

N(D) = N(A) = 1

N(G) = N(C) + N(D) = 1 + 1 = 2

N(H) = N(B) + N(D) = 1 + 1 = 2

N(I) = N(G) + N(H) = 2 + 2 = 4

Важно: Путь через город F нам не нужен. Поэтому мы не учитываем пути, ведущие непосредственно к F или через F.

N(J) = N(I) + N(H) (если бы был путь из H в J, что не показано на схеме, но у нас есть путь из I в J)

N(J) = N(I) = 4

Ответ: 4