Ко­ли­че­ство путей до го­ро­да Х = ко­ли­че­ство путей до­брать­ся в любой из тех го­ро­дов, из ко­то­рых есть до­ро­га в Х.

При этом если путь дол­жен не про­хо­дить через какой-то город, нужно про­сто не учи­ты­вать этот город при под­сче­те сумм. А если город на­о­бо­рот обя­за­тель­но дол­жен ле­жать на пути, тогда для го­ро­дов, в ко­то­рые из нуж­но­го го­ро­да идут до­ро­ги, в сум­мах нужно брать толь­ко этот город.

С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 1 + 1 + 2 = 4

Е = Б + В = 1 + 4 = 5

З = В + Г + Д = 4 + 2 + 1 = 7

Ж = В + Е + З = 4 + 5 + 7 = 16

И = Ж = 16 (E и З не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Ж)

К = И = 16

Л = И = 16

Таким об­ра­зом, путей, про­хо­дя­щих через город Ж, но не про­хо­дя­щих через город К: М = Л = 16.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город Ж, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Ж и ко­ли­че­ства путей из го­ро­да Ж в город М.

Най­дем ко­ли­че­ство путей из го­ро­да А в город Ж:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 1 + 1 + 2 = 4

Е = Б + В = 1 + 4 = 5

З = В + Г + Д = 4 + 2 + 1 = 7

Ж = В + Е + З = 4 + 5 + 7 = 16.

Ни один из этих путей не про­хо­дит через город К.

Из го­ро­да Ж в город М есть толь­ко один путь, не про­хо­дя­щий через город К: Ж—И—Л—М.

Тогда ко­ли­че­ство путей из го­ро­да А в город К=М, про­хо­дя­щих через город Ж, но не про­хо­дя­щих через город К, равно 16 · 1 = 16.

Ответ: 16.

Ко­ли­че­ство путей до го­ро­да Х = ко­ли­че­ство путей до­брать­ся в любой из тех го­ро­дов, из ко­то­рых есть до­ро­га в Х.

При этом если путь дол­жен не про­хо­дить через какой-то город, нужно про­сто не учи­ты­вать этот город при под­сче­те сумм. А если город на­о­бо­рот обя­за­тель­но дол­жен ле­жать на пути, тогда для го­ро­дов, в ко­то­рые из нуж­но­го го­ро­да идут до­ро­ги, в сум­мах нужно брать толь­ко этот город.

С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов:

А = 1.

Б = А = 1.

Д = А = 1.

Г = А + Д = 1 + 1 = 2.

В = А + Б + Г = 1 + 1 + 2 = 4.

Е = Б + В = 1 + 4 = 5.

З = В + Г + Д = 4 + 2 + 1 = 7.

Ж = В + З = 4 + 7 = 11.

И = Ж + З = 11 + 7 = 18.

К = И = 18.

Л = И = 18.

М = Л = 18.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город Л, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Л и ко­ли­че­ства путей из го­ро­да Л в город М.

За­ме­тим, что из го­ро­да Л в город М ведет толь­ко один путь.

За­ме­тим также, что в город Л можно до­брать­ся толь­ко из го­ро­да И.

Таким об­ра­зом, ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город Л, равно ко­ли­че­ству путей из го­ро­да А в город И, при этом, в со­от­вет­ствии с усло­ви­ем за­да­чи, эти до­ро­ги не долж­ны про­хо­дить через город Е.

А = 1.

Б = А = 1.

Д = А = 1.

Г = А + Д = 1 + 1 = 2.

В = А + Б + Г = 1 + 1 + 2 = 4.

З = В + Г + Д = 4 + 2 + 1 = 7.

Ж = В + З = 4 + 7 = 11 (Е не учи­ты­ва­ем, так как путь не дол­жен про­хо­дить через Е).

И = Ж + З = 11 + 7 = 18 (Е не учи­ты­ва­ем, так как путь не дол­жен про­хо­дить через Е).

Ответ: 18.

При­ме­ча­ние.

Ответ 36 не­вер­ный.

Тем, кто его по­лу­чил, ре­ко­мен­ду­ем пе­ре­чи­тать усло­вие и про­ана­ли­зи­ро­вать при­ве­ден­ное ре­ше­ние.