На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого протяженного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.
Посчитаем последовательно количество путей до каждого из пунктов и будем выписывать самый протяженный путь до населенного пункта:
Б = Д = 1;
Г = А − Д = 2;
В = А − Д -Г = 3;
Е = А − Б = 2;
З = А − Д − Г − В = 4;
Ж = А − Д − Г − В − З = 5;
И = А − Д − Г − В − З − Ж = 6;
К = А − Д − Г − В − З − Ж − И = 7;
Л = А − Д − Г − В − З − Ж − И − К = 8;
М = А − Д − Г − В − З − Ж − И − К − Л = 9 (конечный пункт).
Ответ: 9.