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

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

Как будем искать пути?

Нам нужно проследить все возможные маршруты, двигаясь только в направлении стрелок. Будем идти шаг за шагом, записывая все варианты.

Путешествие начинается из А:

1. Из А можно попасть только в Б.

Теперь из Б:

2. Из Б можно попасть в В, Г или Д.

Рассмотрим пути через В:

3. А → Б → В
   Из В можно попасть только в Г.
   А → Б → В → Г
   Из Г можно попасть в Д или Ж.
   
   • А → Б → В → Г → Д
     Из Д можно попасть в Е или Ж.
     
     • А → Б → В → Г → Д → Е
       Из Е можно попасть только в 3. Путь 1: А → Б → В → Г → Д → Е → 3
     • А → Б → В → Г → Д → Ж
       Из Ж можно попасть только в 3. Путь 2: А → Б → В → Г → Д → Ж → 3
   • А → Б → В → Г → Ж
     Из Ж можно попасть только в 3. Путь 3: А → Б → В → Г → Ж → 3

Рассмотрим пути через Г (начав из А → Б → Г):

4. А → Б → Г
   Из Г можно попасть в Д или Ж.
   
   • А → Б → Г → Д
     Из Д можно попасть в Е или Ж.
     
     • А → Б → Г → Д → Е
       Из Е можно попасть только в 3. Путь 4: А → Б → Г → Д → Е → 3
     • А → Б → Г → Д → Ж
       Из Ж можно попасть только в 3. Путь 5: А → Б → Г → Д → Ж → 3
   • А → Б → Г → Ж
     Из Ж можно попасть только в 3. Путь 6: А → Б → Г → Ж → 3

Рассмотрим пути через Д (начав из А → Б → Д):

5. А → Б → Д
   Из Д можно попасть в Е или Ж.
   
   • А → Б → Д → Е
     Из Е можно попасть только в 3. Путь 7: А → Б → Д → Е → 3
   • А → Б → Д → Ж
     Из Ж можно попасть только в 3. Путь 8: А → Б → Д → Ж → 3

Теперь рассмотрим пути, начинающиеся не с А → Б → В, а напрямую из А → Б → Г (или А → Б → Д, но это уже учтено):

Мы уже учли все пути, которые идут через Б. Теперь нужно убедиться, что мы не пропустили ничего.

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

• А: 1 путь (сам город)
• Б: 1 путь (А → Б)
• В: 1 путь (А → Б → В)
• Г: Пути до В + пути до Б (т.к. из В и Б можно попасть в Г) = 1 (через В) + 1 (через Б) = 2 пути.
  (А → Б → В → Г, А → Б → Г)
• Д: Пути до Г + пути до Б (т.к. из Г и Б можно попасть в Д) = 2 (через Г) + 1 (через Б) = 3 пути.
  (А → Б → В → Г → Д, А → Б → Г → Д, А → Б → Д)
• Е: Пути до Д (т.к. из Д можно попасть в Е) = 3 пути.
  (А → Б → В → Г → Д → Е, А → Б → Г → Д → Е, А → Б → Д → Е)
• Ж: Пути до Г + пути до Д (т.к. из Г и Д можно попасть в Ж) = 2 (через Г) + 3 (через Д) = 5 путей.
  (А → Б → В → Г → Ж, А → Б → Г → Ж, А → Б → В → Г → Д → Ж, А → Б → Г → Д → Ж, А → Б → Д → Ж)
• 3: Пути до Е + пути до Ж (т.к. из Е и Ж можно попасть в 3) = 3 (через Е) + 5 (через Ж) = 8 путей.

Проверим по путям, которые мы посчитали вручную:

1. А → Б → В → Г → Д → Е → 3
2. А → Б → В → Г → Д → Ж → 3
3. А → Б → В → Г → Ж → 3
4. А → Б → Г → Д → Е → 3
5. А → Б → Г → Д → Ж → 3
6. А → Б → Г → Ж → 3
7. А → Б → Д → Е → 3
8. А → Б → Д → Ж → 3

Получилось 8 путей. Это совпадает с нашим подсчетом!

Ответ: Существует 8 различных путей из города А в город 3.