1. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город Ж?

Решение.

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

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

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

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

2. На рисунке — схема дорог, связывающих города А, B, C, D, E, G, H, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?

Решение.

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

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

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

A = 1;

B = A = 1;

G = А = 1;

E = A + B + G = 1 + 1 + 1 = 3;

C = B + E = 1 + 3 = 4;

H = G + E = 1 + 3 = 4;

F = E + H = 3 + 4 = 7;

D = E + C + F = 3 + 4 + 7 = 14.

Ответ: 14.

3. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город В?

Решение.

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

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

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

А = 1

Б = А = 1

В = А + Б = 2

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

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

Е = В + Д = 4

Ж = В + Г = 4

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

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

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

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

А = 1

Б = А = 1

В = А + Б = 2

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

В = 1

Г = В = 1

Ж = В + Г =1 + 1 = 2

Д = В = 1

Е = В + Д = 1 + 1 = 2

К = Д + Е + Ж = 1 + 2 + 2 = 5

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

Ответ: 10.

4. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город П, проходящих через город В?

Решение.

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

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

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

5. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город Г?

Решение.

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

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

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

А = 1.

Д = А = 1.

Г = А + Д = 2.

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

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

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

Ж = В + Е + З = 8.

И = Е + Ж + З = 14.

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

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

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

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

А = 1.

Д = А = 1.

Г = А + Д = 2.

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

Г = 1.

В = Г = 1.

Е = В = 1.

З = В + Г = 2.

Ж = В + Е + З = 4.

И = Е + Ж + З = 7.

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

Ответ: 14.

6. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Решение.

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

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

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

А = 1;

Б = А = 1;

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

Д = А = 1;

Г = А + В = 1 + 2 = 3;

Е = Б + В = 1 + 2 = 3;

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

З = В + Г + Е + Ж = 2 + 3 + 3 + 4 = 12;

И = Е = 3;

К = Ж = 4;

Л = Е + Ж + З + И + К = 3 + 4 + 12 + 3 + 4 = 26.

Ответ: 26.

7. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город К, не проходящих через пункт В?

Решение.

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

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

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

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

Ж = Д = 1.

И = Г = 1.

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

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

Ответ: 5.

8. На рисунке — схема дорог, связывающих города А, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?

Решение.

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

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

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

A = 1;

B = A = 1;

F = А = 1;

E = A + B + F = 1 + 1 + 1 = 3;

C = B = 1;

G = F + E = 1 + 3 = 4;

H = G = 4;

D = B + E + C + G + H = 1 + 3 + 1 + 4 + 4 = 13.

Ответ: 13.

9. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город К, не проходящих через пункт В?

Решение.

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

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

А = 1.

Б = А = 1.

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

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

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

Ж = Д = 1.

И = Г + Е = 3.

К = Д + Ж + И = 5.

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

Ответ: 5.

10. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

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

Решение.

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

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

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

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

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

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

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

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

11. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Решение.

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

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

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

А = 1;

Б = А = 1;

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

Д = А = 1;

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

Е = Б + В = 1 + 2 = 3;

Ж = Г + Д = 2 + 1 = 3;

З = В + Г + Е + Ж = 2 + 2 + 3 + 3 = 10;

И = Е = 3;

К = Ж = 3;

Л = Ж + З + И + К = 3 + 10 + 3 + 3 = 19.

Ответ: 19.

12. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город З?

Решение.

Количество путей до города 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.

13. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город В?

Решение.

Количество путей до города 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.

14. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город П, проходящих через город Н?

Решение.

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

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

15. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город П, проходящих через город М?

Решение.

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

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

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

16. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город Ж?

Решение.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б + В = 5

З = Д = 1

Ж = Е + В + Г + Д + З = 5 + 4 + 2 + 1 + 1 = 13

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

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б + В = 5

З = Д = 1

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

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

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

Ответ: 13.

17. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт К, не проходящих через пункт Е?

Решение.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = Б + В = 3.

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

Ж = Д = 3.

К = Ж + И + Д = 11.

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

Ответ: 11.

18. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, проходящих через пункт И?

Решение.

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

Е = Д + Г = 5.

И = Г + Е + В = 10.

К = И = 10.

Л = К = 10.

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

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

Е = Д + Г = 5.

И = Г + Е + В = 10.

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

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

Ответ: 10.

19. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, не проходящих через пункт Е?

Решение.

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

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

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

А = 1.

Б = А = 1.

В = А = 1.

Г = А + Б + В = 3.

Д = Г = 3.

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

Ж = Д = 3.

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

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

Ответ: 9.

20. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Г?

Решение.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

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

Ж = Е = 3.

И = Е + Г = 6.

К = И + Ж = 9.

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

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

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

Г = 1.

Е = Г = 1.

Ж = Е = 1.

И = Е + Г = 2.

К = И + Ж = 3.

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

Ответ: 9.

21. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Д?

Решение.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

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

Ж = Д + Е = 6.

И = Е = 3.

К = Ж + И = 9.

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

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

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

Д = 1.

Е = Д = 1.

Ж = Д + Е = 2.

И = Е = 1.

К = Ж + И = 3.

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

Ответ: 9.

22. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, проходящих через пункт Е?

Решение.

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

И = Г + В = 5.

Е = Д + Г + И = 10.

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

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

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

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

И = Г + В = 5.

Е = Д + Г + И = 10.

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

Е = 1.

К = Е = 1.

Д = Е + К = 2.

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

Ответ: 20.

23. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

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

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

А = 1;

Б = А = 1;

Г = А = 1;

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

Д = Б = 1;

Е = Г = 1;

К = Б + В + Г + Д + Е = 1 + 2 + 1 + 1 + 1 = 6.

Ответ: 6.

24. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Г?

Решение.

Количество путей до города 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.

25. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город B?

Решение.

Количество путей до города 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.

ОГЭ информатика 9 задание