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