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

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

• A = 1
• Б = 1
• В = 1
• Г = 1
• Ж = 1+1 = 2
• Е = 1+1 = 2
• З = 2+2 = 4
• И = 4+2 = 6
• К = 6+2 = 8

Ответ: 8