Условие:
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Л и проходящих через город Ж, но НЕ проходящих через город 3 ?
Решение:
Ниже приведён один из вариантов рассуждения, который позволяет получить ответ. Заметим, что для решения задачи удобно разбить путь из города А в город Л на два отрезка – от А до города Ж (при этом путь не должен содержать запрещённый город 3) и от города Ж до города Л (также без прохождения через 3). Тогда искомое число путей равно числу путей от А до Ж (без 3), умноженному на число путей от Ж до Л (без 3). Предположим, что схема дорог следующая (при этом все дороги направлены так, как заданы стрелками): 1. Города упорядочены так: А, Б, В, Г, Д, Е, Ж, 3, И, К, Л. 2. Из города А можно попасть...