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

Решение:

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

1. Из города А можно попасть только в город Б. Количество путей до Б = 1.

2. Из города Б можно попасть в города В и Г. Количество путей до В = 1. Количество путей до Г = 1.

3. Из города В можно попасть только в город Г. Количество путей до Г, проходящих через В = 1. Итого путей до Г = 1 (из Б) + 1 (через В) = 2.

4. Из города Г можно попасть в города Ж, И и Л. Количество путей до Ж = 2. Количество путей до И = 2. Количество путей до Л = 2.

5. Из города Ж можно попасть в города З и Л. Количество путей до З = 2. Количество путей до Л, проходящих через Ж = 2. Итого путей до Л = 2 (из Г) + 2 (через Ж) = 4.

6. Из города И можно попасть в города З и Л. Количество путей до З, проходящих через И = 2. Итого путей до З = 2 (из Ж) + 2 (из И) = 4.

7. Количество путей до Л, проходящих через И = 2. Итого путей до Л = 4 (из Г) + 2 (из И) + 4 (из Ж) = 10.

8. Учтем путь до города Е. Из города Д можно попасть в Е. Путей до Д = 2 (из Г). Количество путей до Е = 2.

9. Из города Е можно попасть в Л. Количество путей до Л, проходящих через Е = 2. Итого путей до Л = 10 (из Г, Ж, И) + 2 (через Е) = 12.

10. Также из города Г есть прямой путь в Л. Количество путей до Л = 12 (предыдущие) + 2 (из Г) = 14.

Давайте пересчитаем более систематически:

А: 1

Б: 1

В: 1

Г: Б->Г (1) + В->Г (1) = 2

Ж: Г->Ж (2)

Д: Г->Д (2)

И: Г->И (2)

З: Ж->З (2) + И->З (2) = 4

Е: Д->Е (2)

Л: Г->Л (2) + Ж->Л (2) + И->Л (2) + Е->Л (2) = 8

Уточняем пути до Л:

А → Б (1)

Б → В (1)

Б → Г (1)

В → Г (1)

Пути до Г: 1 (из Б) + 1 (из В) = 2

Пути до Ж: из Г → 2

Пути до Д: из Г → 2

Пути до И: из Г → 2

Пути до Е: из Д → 2

Пути до З: из Ж → 2; из И → 2. Всего до З = 2 + 2 = 4

Пути до Л:

Из Г: 2

Из Ж: 2

Из И: 2

Из Е: 2

Всего путей до Л = 2 + 2 + 2 + 2 = 8.

Ответ: 8