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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

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

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

З = 0 (по­сколь­ку в З не ведет ни одна до­ро­га из В)

И = Е + Ж = 4 + 8 = 12.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4.

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

В = 1

Е = В = 1

Ж = В + Е = 1 + 1 = 2

И = Е + Ж = 1 + 2 = 3.

Тогда ко­ли­че­ство путей из го­ро­да А в город И, про­хо­дя­щих через город В, равно 4 · 3 = 12.

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

Ответ: 12.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = В = 4 (Б не учи­ты­ва­ем, т. к. там не про­хо­дим через В)

З = В = 4 (Д и Г не учи­ты­ва­ем по тому же прин­ци­пу)

Ж = В + Е + З = 4 + 4 + 4 = 12

И = Е + Ж + З = 4 + 12 + 4 = 20.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4.

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

В = 1

Е = В = 1

З = В = 1

Ж = В + Е + З = 1 + 1 + 1 = 3

И = Е + Ж + З = 1 + 3 + 1 = 5.

Тогда ко­ли­че­ство путей из го­ро­да А в город И, про­хо­дя­щих через город В, равно 4 · 5 = 20.

Ответ: 20.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б = 1

З = Д = 1

Ж = Б + В + Г+ Д + Е + З = 1 + 4 + 2 + 1 + 1 + 1 = 10

И = Ж = 10 (путь в И через З и Е не учи­ты­ва­ем, т. к. надо прой­ти через Ж).

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б = 1

З = Д = 1

Ж = Б + В + Г+ Д + Е + З = 1 + 4 + 2 + 1 + 1 + 1 = 10.

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

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

Ответ: 10.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

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

Ж = Д + Е = 6.

И = Е = 3.

К = Ж + И = 9.

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

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

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

Д = 1.

Е = Д = 1.

Ж = Д + Е = 2.

И = Е = 1.

К = Ж + И = 3.

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

Ответ: 9.

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

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

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

А = 1.

Д = А = 1.

Г = А + Д = 2.

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

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

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

Ж = В + Е + З = 8.

И = Е + Ж + З = 14.

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

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

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

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

А = 1.

Д = А = 1.

Г = А + Д = 2.

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

Г = 1.

В = Г = 1.

Е = В = 1.

З = В + Г = 2.

Ж = В + Е + З = 4.

И = Е + Ж + З = 7.

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

Ответ: 14.

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

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

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

А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Г = 1 + 2 = 3

Б = А + В = 1 + 3 = 4

Е = Б = 4

З = Д + Г + В = 1 + 2 + 3 = 6

Ж = Е + Б + В + З = 4 + 4 + 3 + 6 = 17

И = Ж = 17 (учи­ты­ва­ем толь­ко город, через ко­то­рый дол­жен про­хо­дить путь)

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

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

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

А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Г = 1 + 2 = 3

Б = А + В = 1 + 3 = 4

Е = Б = 4

З = Д + Г + В = 1 + 2 + 3 = 6

Ж = Е + Б + В + З = 4 + 4 + 3 + 6 = 17.

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

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

Ответ: 17.

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

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

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

А = 1.

Б = А = 1.

Г = А = 1.

Д = Б = 1.

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

Ж = Д = 1.

И = Г + Е = 2.

К = Ж + Е + И + Д = 5.

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

Ответ: 5.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = Б + В = 3.

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

Ж = Д = 3.

К = Ж + И + Д = 11.

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

Ответ: 11.

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

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

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

А = 1.

Б = А = 1.

В = А = 1.

Г = А + Б + В = 3.

Д = Г = 3.

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

Ж = Д = 3.

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

Л = Д + Ж + К = 3 + 3 + 3 = 9 (Е не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город Е).

Ответ: 9.

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

Е = Д + Г = 5.

И = Г + Е + В = 10.

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

Л = К = 10.

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

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

Е = Д + Г = 5.

И = Г + Е + В = 10.

Из пунк­та И в пункт Л есть толь­ко один путь И - К - Л.

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

Ответ: 10.

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

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

K = Ж = 8

Н = Ж = 8

М = Ж + Н = 16

Л = К + Ж + М = 8 + 8 + 16 = 32

П = Л = 32 (так как ищем пути про­хо­дя­щие через город Л).

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

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

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

Ж = 1

Н = К = Ж = 1

М = Ж + Н = 2

Л = К + Ж + М = 4.

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

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

Ответ: 32.

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

А = 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.

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

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

Ж = 1.

К = Ж = 1.

Н = Ж = 1.

М = Ж + Н = 2.

Л = К + Ж + М = 4.

П = К + Л + М = 7.

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

Ответ: 21.

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Л = Ж + К= 19.

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

Л = 1.

М = Л = 1.

П = Л + М = 2.

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Н = Д + Ж = 9.

М = Ж + Н = 17.

Л = М = 17 (Ж и К не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через М).

П = Л + М = 34 (К не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через М).

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

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Н = Д + Ж = 9.

М = Ж + Н = 17.

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

М = 1.

Л = М = 1.

П = Л + М = 2.

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

Ответ: 34.

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

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

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

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

Ж = Д = 1.

И = Г = 1.

К = Д + Ж + И + Е = 5.

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

Ответ: 5.

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

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

А = 1.

Б = А = 1.

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

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

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

Ж = Д = 1.

И = Г + Е = 3.

К = Д + Ж + И = 5.

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

Ответ: 5.

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

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

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

А = 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.

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

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

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

А = 1

Б = А = 1

В = А + Б = 2

Г = Б = 1

Д = Б + В = 3

Ж = Б + Г + Д = 5

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

К = Е + Ж = 5+ 5 = 10 ( Д не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через город Ж).

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

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

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

А = 1

Б = А = 1

В = А + Б = 2

Г = Б = 1

Д = Б + В = 3

Ж = Б + Г + Д = 5.

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

Ж = 1

Е = Ж = 1

К = Ж + Е = 2.

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

Ответ: 10.

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

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

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

А = 1;

Б = А = 1;

В = А + Б = 1 + 1 = 2;

Д = А = 1;

Г = А + В + Д = 1 + 2 +1 = 4;

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

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

К = Ж = 4;

Л = Ж + З + К = 4 + 8 + 4 = 16. (И не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

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

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

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

А = 1;

Б = А = 1;

В = А + Б = 1 + 1 = 2;

Д = А = 1;

Г = А + В + Д = 1 + 2 +1 = 4;

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

Г = 1;

Ж = Г = 1;

З = Г + Ж = 1 + 1 = 2;

К = Ж = 1;

Л = Ж + З + К = 1 + 2 + 1 = 4;

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

Ответ: 16.

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

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

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

А = 1;

Б = А = 1;

Д = А = 1;

Г = А + Д = 1 + 1 = 2;

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

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

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

И = Е = 5;

Л = И + Е + З = 5 + 5 + 5 = 15.

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

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

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

А = 1;

Б = А = 1;

Д = А = 1;

Г = А + Д = 1 + 1 = 2;

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

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

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

Е = 1;

З = Е = 1;

И = Е = 1;

Л = И + Е + З = 3.

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

Ответ: 15.

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

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

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

А = 1;

Б = А = 1;

В = А + Б = 1 + 1 = 2;

Д = А = 1;

Г = А + В + Д = 1 + 2 +1 = 4;

Е = Б = 1;

Ж = Г + Д = 4 + 1 = 5;

З = В + Г + Е + Ж = 2 + 4 + 1 + 5 = 12;

Л = З = 12.

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

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

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

А = 1;

Б = А = 1;

В = А + Б = 1 + 1 = 2;

Д = А = 1;

Г = А + В + Д = 1 + 2 +1 = 4;

Е = Б = 1;

Ж = Г + Д = 4 + 1 = 5;

З = В + Г + Е + Ж = 2 + 4 + 1 + 5 = 12.

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

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

Ответ: 12.

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

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

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

А = 1;

Б = А = 1;

В = А + Б = 1 + 1 = 2;

Д = А = 1;

Г = В = 2;

Е = В = 2;

Ж = Г = 2;

З = В + Г + Е = 2 + 2 + 2 = 6;

И = Е = 2;

К = Ж = 2;

Л = Е + Ж + З + И + К = 2 + 2 + 6 + 2 + 2 = 14.

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

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

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

А = 1;

Б = А = 1;

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

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

В = 1;

Е = В = 1;

Ж = Г = 1;

З = В + Г + Е = 3;

И = Е = 1;

К = Ж = 1;

Л = Е + Ж + З + И + К = 7.

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

Ответ: 14.

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

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

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

А = 1;

Б = А = 1;

В = А + Б = 1 + 1 = 2;

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

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

Е = В + Д = 2 + 2 = 4;

Ж = В + Г = 2 + 2 = 4;

К = Д + Е + Ж = 2 + 4 + 4 = 10.

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

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

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

А = 1;

Б = А = 1;

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

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

В = 1;

Г = В = 1;

Д = В = 1;

Е = В + Д = 2;

Ж = В + Г = 2;

К = Д + Е + Ж = 5.

Тогда ко­ли­че­ство путей из го­ро­да А в город К, про­хо­дя­щих через город В, равно 2 · 5 = 10.

Ответ: 10.