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

Решение:

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

• А: 1 путь (сам город А).
• Б: 1 путь (А → Б).
• Г: 1 путь (А → Б → Г).
• В: 1 путь (А → В).
• Е: 1 путь (А → В → Е).
• Ж: Пути до Ж: (А → Б → Г → Ж) + (А → В → Ж). Всего 1 + 1 = 2 пути.
• И: Пути до И: (А → Б → Г → Ж → И) + (А → В → Ж → И). Всего 2 + 1 = 3 пути.
• К: Пути до К: (А → В → Е → К) + (А → Б → Г → Ж → И → К) + (А → В → Ж → И → К). Всего 1 + 2 + 1 = 4 пути.
• Л: Пути до Л: (А → В → Е → К → Л) + (А → Б → Г → Ж → И → К → Л) + (А → В → Ж → И → К → Л). Всего 1 + 2 + 4 = 7 путей.
• Важно: Пути, проходящие через город Д, не учитываются. В данной схеме город Д доступен из Г, но мы не строим путь через него, чтобы попасть в Л.

Ответ: 7