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