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