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

Решение:

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

А: 1 (начальная точка)

Б: 1 (из А)

Г: 1 (из А)

В: 1 (из Б)

Е: 1 (из Г) + 1 (из В) = 2

Ж: 2 (из Е)

З: 1 (из Ж)

И: 2 (из Е)

К: 1 (из Ж) + 1 (из И) = 2

Ответ: 2