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

Решение:

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

• Город А: Из города А можно сразу попасть в города Б и Г. Количество путей в А = 1 (мы находимся там).
• Город Б: Из А можно попасть в Б. Стрелки из других городов не ведут в Б. Количество путей в Б = 1 (А → Б).
• Город В: Из Б можно попасть в В. Количество путей в В = Количество путей в Б = 1 (А → Б → В).
• Город Г: Из А можно попасть в Г. Количество путей в Г = 1 (А → Г).
• Город Д: Из Б и Г можно попасть в Д. Количество путей в Д = Количество путей в Б + Количество путей в Г = 1 + 1 = 2 (А → Б → Д; А → Г → Д).
• Город Е: Из Д можно попасть в Е. Количество путей в Е = Количество путей в Д = 2 (А → Б → Д → Е; А → Г → Д → Е).
• Город Ж: Из В и Д можно попасть в Ж. Количество путей в Ж = Количество путей в В + Количество путей в Д = 1 + 2 = 3 (А → Б → В → Ж; А → Б → Д → Ж; А → Г → Д → Ж).
• Город 3: Из Е и Ж можно попасть в 3. Количество путей в 3 = Количество путей в Е + Количество путей в Ж = 2 + 3 = 5.

Пути из города А в город 3:

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

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