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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

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

Е = Б + В = 1 + 4 = 5

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

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

И = Ж = 16

К = И = 16

Л = И = 16

Таким об­ра­зом, путей, про­хо­дя­щих через город Ж, но не про­хо­дя­щих через город К: М = Л = 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.

Ответ: 18.

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

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

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

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

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

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

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

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

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

А = 1

Б = А = 1

Г = А + Б = 1 + 1 = 2 (т. к. про­хо­дить через город нужно Г обя­за­тель­но)

Д = Г = 2

Ж = Г + Д = 4 (т. к. нель­зя про­хо­дить через город З)

И = Д = 2

К = Ж + Д + И = 8

Ответ: 8.

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

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

Из го­ро­да А в город Г есть 2 пути: А—Г и А—Б—Г.

Най­дем ко­ли­че­ство путей из го­ро­да Г в город К (при этом Г - ис­ход­ный пункт). По усло­вию, эти пути не долж­ны про­хо­дить через город З.

Г = 1

Д = Г = 1

Ж = Г + Д = 2

И = Д = 1

К = Ж + Д + И = 4.

Таким об­ра­зом, ко­ли­че­ство путей из го­ро­да А в город К, про­хо­дя­щих через город Г и не про­хо­дя­щих через город З, равно 2 · 4  =  8.

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

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

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

А = 1

Б = А = 1

В = А = 1

Г = А + Б + В = 3

Д = Г = 3 (Б не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через город Г)

Е = Д + Г = 6

Ж = Д = 3

И = Г + Е = 9

К = Е + И = 15

М = К = 15

Н = Ж = 3

П = Н + М = 18

Те­перь найдём по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов, про­хо­дя­щих через пункт Л, но не про­хо­дя­щих через пункт Г:

А = 1

Б = А = 1

Д = Б = 1

Е = Д = 1

Ж = Д = 1

Л = Д + Е + Ж = 3

М = Л = 3

Н = Л = 3

П = Л + М + Н = 9

Таким об­ра­зом, ответ  — 18 + 9 = 27.

Ответ: 27.

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

В за­да­че тре­бу­ет­ся найти ко­ли­че­ство путей, ко­то­рые либо про­хо­дят через пункт Г, но не про­хо­дят через пункт Л, либо про­хо­дят через пункт Л, но не про­хо­дит через пункт Г. Тем, у кого в ре­зуль­та­те ре­ше­ния дан­ной за­да­чи по­лу­ча­ет­ся ответ, от­лич­ный от 27, ре­ко­мен­ду­ем про­ве­рить, все ли най­ден­ные пути удо­вле­тво­ря­ют этим усло­ви­ям.

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

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

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

А = 1

Б = А = 1

В = А = 1

Г = А + Б + В = 3

Д = Г = 3 (Б не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

Ж = Д = 3

И = Г = 3

К = И = 3

Л = Д + Ж = 6

М = К + Л = 9

Н = Ж + Л = 9

П = Н + М + Л = 24

Те­перь найдём по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов, про­хо­дя­щих через пункт Е, но не про­хо­дя­щих через пункт Г:

А = 1

Б = А = 1

Д = Б = 1

Е = Д = 1

И = Е = 1

Ж = Д = 1

К = И + Е = 2

Л = Е = 1

М = Л + К = 3

Н = Л = 1

П = Л + М + Н = 5

Таким об­ра­зом, ответ  — 24 + 5 = 29.

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

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

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

А = 1

Б = А = 1

В = А = 1

Г = А + Б + В = 3.

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

Г = 1

Д = Г = 1

Ж = Д = 1

И = Г = 1

К = И = 1

Л = Д + Ж = 2

М = К + Л = 3

Н = Ж + Л = 3

П = Н + М + Л = 8.

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

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

За­ме­тим, что су­ще­ству­ет един­ствен­ный путь из А в Е, не про­хо­дя­щий через Г. Это путь А—Б—Д—Е.

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

Е = 1

И = Е = 1

К = Е + И = 2

Л = Е = 1

М = К + Л = 2 + 1 = 3

Н = Л = 1

П = Л + М + Н = 1 + 3 + 1 = 5.

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

Таким об­ра­зом, ответ  — 24 + 5 = 29.

Ответ: 29.

Ре­ше­ние. За­ме­тим, что до точки Б можно дойти по пути длины 3: А—В—Г—Б. Далее пойдём в Д. Чтобы путь по­лу­чил­ся самым длин­ным, из Д нам не­об­хо­ди­мо пойти в Ж, а затем в Н. Далее не­об­хо­ди­мо прой­ти по пути Н—Л—М—П. Окон­ча­тель­но, путь будет вы­гля­деть так: А—В—Г—Б—Д—Ж—Н—Л—М—П. Длина пути  — 9.

Ответ: 9.

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

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

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

А = 1

Б = А = 1

В = А = 1

Г = А + Б + В = 1 + 1 + 1 = 3

Д = Г = 3 (Б не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

И = Г = 3

Ж = Д = 3

К = И = 3

Л = Д + Ж = 6

М = К + Л = 9

Н = Ж + Л = 9

П = Л + М + Н = 24

Ответ: 24.

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

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

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

А = 1

Б = А = 1

В = А = 1

Г = А + Б + В = 1 + 1 + 1 = 3.

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

Г = 1

Д = Г = 1

И = Г = 1

Ж = Д = 1

К = И = 1

Л = Д + Ж = 2

М = К + Л = 3

Н = Ж + Л = 3

П = Л + М + Н = 8.

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

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

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

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

А = 1

Б = А = 1

В = А = 1

Г = А + Б + В = 1 + 1 + 1 = 3

Д = Б + Г = 4

Е = Г + Д = 7

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

К = Е + И = 14

М = К = 14

П = М = 14

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

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

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

А = 1

Б = А = 1

В = А = 1

Г = А + Б + В = 1 + 1 + 1 = 3

Д = Б + Г = 4

Е = Г + Д = 7.

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

Е = 1

И = Е = 1

К = Е + И = 2

М = К = 2

П = М = 2

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

Ответ: 14.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 2

В = А + Б + Г = 4

Е = Б = 1

З = Д = 1

Ж = В + Г + Д + Е + З = 9

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

Л = И = 9

М = И + Л = 18

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

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 2

В = А + Б + Г = 4

Е = Б = 1

З = Д = 1

Ж = В + Г + Д + Е + З = 9.

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

Сле­до­ва­тель­но, ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город Ж и не про­хо­дя­щих через город К, равно 9 · 2  =  =18.

Ответ: 18.

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

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

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

А = 1

Г = А = 1

В = А + Г = 2

Б = В = 2 (А не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через В)

Д = Б = 2

Е = Б + В = 4

И = Е = 4

Л = Б + Е = 6

К = Д + Л = 8

М = И + К = 12

Н = И + М = 16

П = К = 8

Р = Н = 16

С = К + М + П + Р = 44

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

Ответ: 44.

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

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

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

А = 1

Г = А = 1

В = А + Г = 2

Б = А + В = 3

Е = Б + В + Г = 6

Л = Е = 6

И = Е = 6

Ж = Е + Л + И = 18

К = Л + Ж = 24

Н = И = 6

П = К = 24

Р = Н = 6

С = К + П + Р = 54

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

Ответ: 54.

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

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

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

А = 1

Г = А = 1

В = А + Г = 2

Б = А + В = 3

Е = Б + В + Г = 6

Най­дем ко­ли­че­ство путей из го­ро­да Е в город С, ко­то­рые не про­хо­дят через город М (при этом Е  — ис­ход­ный пункт):

Е = 1

Л = Е = 1

И = Е = 1

Ж = Е + Л + И =3

К = Л + Ж = 4

Н = И = 1

П = К = 4

Р = Н = 1

С = К + П + Р = 9

Сле­до­ва­тель­но, ко­ли­че­ство путей из го­ро­да А в город С, не про­хо­дя­щих через город М, равно 6 · 9  =  54.