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

Решение:

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

Пути из А:

• В город Б: 1 путь (А → Б).
• В город В: 1 путь (А → В).

Пути из Б:

• В город Д: 1 путь (А → Б → Д).

Пути из В:

• В город Г: 1 путь (А → В → Г).
• В город Д: 1 путь (А → В → Д).

Пути в город Г:

• Из А: 0 путей.
• Из В: 1 путь (А → В → Г).
• Всего в Г: 1 путь.

Пути в город Д:

• Из Б: 1 путь (А → Б → Д).
• Из В: 1 путь (А → В → Д).
• Всего в Д: 1 + 1 = 2 пути.

Пути в город Е:

• Из Г: 1 путь (А → В → Г → Е).
• Из Д: 2 пути (А → Б → Д → Е и А → В → Д → Е).
• Всего в Е: 1 + 2 = 3 пути.

Пути в город Ж:

• Из Д: 2 пути (А → Б → Д → Ж и А → В → Д → Ж).
• Из Е: 3 пути (А → В → Г → Е → Ж, А → Б → Д → Е → Ж, А → В → Д → Е → Ж).
• Всего в Ж: 2 + 3 = 5 путей.

Ответ: 5