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

Для решения задачи будем считать количество путей, ведущих в каждый город, начиная с города А. Будем обозначать количество путей в город X как N(X).

• N(A) = 1 (начальная точка)
• N(Б) = N(A) = 1
• N(Г) = N(A) = 1
• N(В) = N(Б) = 1
• N(Ж) = N(Г) + N(В) = 1 + 1 = 2
• N(E) = N(B) = 1
• N(K) = N(E) + N(Ж) = 1 + 2 = 3

Мы не учитываем город Д, так как по условию пути не должны через него проходить.

Ответ: 3