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

Решение:

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

• А: 1 путь (начало).
• Б: 1 путь (из А).
• В: 1 путь (из А).
• Г: 1 путь (из Б).
• Д: Пути из А в Д: А→Б→Д (1), А→В→Д (1). Всего 2 пути.
• Е: Пути из А в Е: А→Б→Е (1), А→В→Е (1). Всего 2 пути.
• Ж: Пути из А в Ж: А→Б→Г→Ж (1). Всего 1 путь.
• 3: Пути из А в 3: А→Б→Д→3 (1), А→В→Д→3 (1), А→Б→Е→3 (1), А→В→Е→3 (1).
• Суммируем пути, ведущие в 3: Пути, проходящие через Д (2 пути) + Пути, проходящие через Е (2 пути) = 4 пути.

Ответ: 4