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

Решение:

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

Город А: 1 путь (начальная точка).

Город Б: Из А в Б ведет 1 дорога. Количество путей в Б = 1.

Город В: Из А в В ведет 1 дорога. Количество путей в В = 1.

Город Г: Из А в Г дороги нет. Из Б в Г ведет 1 дорога. Количество путей в Г = Количество путей в Б = 1.

Город Д: Из А в Д дороги нет. Из Б в Д ведет 1 дорога. Из В в Д ведет 1 дорога. Количество путей в Д = Количество путей в Б + Количество путей в В = 1 + 1 = 2.

Город Е: Из А в Е ведет 1 дорога. Количество путей в Е = 1.

Город Ж: Из Д в Ж ведет 1 дорога. Из Е в Ж ведет 1 дорога. Количество путей в Ж = Количество путей в Д + Количество путей в Е = 2 + 1 = 3.

Город З: Из Г в З ведет 1 дорога. Из Ж в З ведет 1 дорога. Количество путей в З = Количество путей в Г + Количество путей в Ж = 1 + 3 = 4.

Итоговый подсчет:

• А: 1
• Б: 1 (из А)
• В: 1 (из А)
• Г: 1 (из Б)
• Д: 2 (из Б, из В)
• Е: 1 (из А)
• Ж: 3 (из Д, из Е)
• З: 4 (из Г, из Ж)

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