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

Ответ: 5

Разбираемся:

Путь 1: A -> Б -> B -> K -> Л -> П

Путь 2: A -> Б -> B -> Ж -> Л -> П

Путь 3: A -> Г -> E -> Ж -> Л -> П

Путь 4: A -> Г -> E -> Ж -> M -> П

Путь 5: A -> Д -> E -> Ж -> Л -> П

Путь 6: A -> Д -> E -> Ж -> M -> П

Получается 6 путей, но путь A -> Г -> E -> Ж -> Л -> П и путь A -> Д -> E -> Ж -> Л -> П можно объеденить и посчитать как один, так как они совпадают после Е

Путь 7: A -> Д -> E -> Ж -> M -> П и A -> Г -> E -> Ж -> M -> П можно объеденить и посчитать как один, так как они совпадают после Е

Итого имеем 5 путей

Ответ: 5