9. На рисунке – схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город О?

Решение: Обозначим количество путей, ведущих в каждый город, числом, написанным внутри города. * Из города А в город Б можно попасть 1 способом. * Из города А в город Г можно попасть 1 способом. * В город В можно попасть из А (1 способ) и из Б (1 способ). 1 + 1 = 2 способа. * В город Д можно попасть из А (1 способ) и из Г (1 способ). 1 + 1 = 2 способа. * В город Е можно попасть из Б (1 способ), из В (2 способа) и из Д (2 способа). 1 + 2 + 2 = 5 способов. * В город Ж можно попасть из Б (1 способ) и из Е (5 способов). 1 + 5 = 6 способов. * В город И можно попасть из Е (5 способов) и из Д (2 способа). 5 + 2 = 7 способов. * В город К можно попасть из Д (2 способа), из И (7 способов) и из Г (1 способ). 2 + 7 + 1 = 10 способов. * В город Л можно попасть из Ж (6 способов), из Е (5 способов) и из И (7 способов). 6 + 5 + 7 = 18 способов. * В город М можно попасть из Ж (6 способов) и из Л (18 способов). 6 + 18 = 24 способа. * В город Н можно попасть из И (7 способов), из К (10 способов) и из Л (18 способов). 7 + 10 + 18 = 35 способов. * В город О можно попасть из Л (18 способов), из М (24 способа) и из Н (35 способов). 18 + 24 + 35 = 77 способов. Ответ: 77