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

Решение:

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

Количество путей из А:

• А: 1
• Б: 1 (из А)
• Г: 1 (из А)
• В: 1 (из А)
• Д: 1 (из А)
• Е: 1 (из А)
• Ж: Пути из В и Б ведут в Ж. Количество путей в Ж = (пути в В) + (пути в Б) = 1 + 1 = 2.
• И: Пути из Е, Ж и З ведут в И. Количество путей в И = (пути в Е) + (пути в Ж) + (пути в З).

Нужно найти количество путей из А в Ж, а затем использовать это значение для подсчета путей до И.

Подсчитаем количество путей до Ж:

• А → 1
• Б → 1 (А)
• В → 1 (А)
• Г → 1 (А)
• Д → 1 (А)
• Е → 1 (А)
• Ж ← Б (1) + В (1) = 2

Теперь подсчитаем количество путей до И, проходящих через Ж:

• Пути из А в И, проходящие через Ж: (Пути из А в Ж) * (Пути из Ж в И).

Из схемы видно, что из Ж можно попасть в И напрямую. Также из других городов есть пути в И.

Нам нужно найти пути из А в И, проходящие через Ж. Это означает, что мы должны дойти до Ж, а потом из Ж дойти до И. Количество путей до Ж равно 2. Количество путей из Ж в И равно 1.

Следовательно, количество путей из А в И, проходящих через Ж = (Пути из А в Ж) * (Пути из Ж в И) = 2 * 1 = 2.

Ответ: 2