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

Решение:

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

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

Ответ: 4