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

Решение:

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

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

  Суммируем пути в город К:

  • Пути через Ж: 3
  • Пути через И: 2
  • Пути через 3: 2
  • Пути через Е: 2

  Всего путей в город К: 3 + 2 + 2 + 2 = 9 путей.

Ответ: 9