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

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8

Н = Ж = 8

М = Н = 8 (так как ищем пути про­хо­дя­щие через город Н)

Л = М = 8

П = Л + М = 16.

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

За­ме­тим, что путь из го­ро­да А в город П обя­за­тель­но дол­жен про­хо­дить через город Ж. По усло­вию за­да­чи путь дол­жен также про­хо­дить через город Н. Тогда ко­ли­че­ство путей из го­ро­да А в город П, про­хо­дя­щих через город Н, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Ж, ко­ли­че­ства путей из го­ро­да Ж в город Н и ко­ли­че­ства путей из го­ро­да Н в город П.

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8.

Из го­ро­да Ж в город Н ведет толь­ко один путь.

Най­дем ко­ли­че­ство путей из го­ро­да Н в город П (при этом Н - ис­ход­ный пункт):

Н = 1

М = Н = 1

Л = М = 1

П = Л + Н = 2.

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

Ответ: 16.

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = Е = 3. (В и Г не учи­ты­ва­ем, по­сколь­ку в этих вер­ши­нах не про­хо­дим через Е).

К = Ж = 3.

Н = Ж = 3.

М = Ж + Н = 6.

Л = К + Ж + М = 12.

П = К + Л + М = 21.

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

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

За­ме­тим, что путь из го­ро­да А в город П обя­за­тель­но дол­жен про­хо­дить через город Ж. По усло­вию за­да­чи путь дол­жен также про­хо­дить через город Е. Тогда ко­ли­че­ство путей из го­ро­да А в город П, про­хо­дя­щих через город Е, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Е, ко­ли­че­ства путей из го­ро­да Е в город Ж и ко­ли­че­ства путей из го­ро­да Ж в город П.

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Из го­ро­да Е в город Ж есть толь­ко один путь.

Най­дем ко­ли­че­ство путей из го­ро­да Ж в город П (при этом Ж - ис­ход­ный пункт):

Ж = 1.

К = Ж = 1.

Н = Ж = 1.

М = Ж + Н = 2.

Л = К + Ж + М = 4.

П = К + Л + М = 7.

Тогда ко­ли­че­ство путей из го­ро­да А в город П, про­хо­дя­щих через город Е, равно 3 · 1 · 7 = 21.

Ответ: 21.