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

Решение:

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

Проанализируем схему и посчитаем количество путей, ведущих к городу К:

1. Из города А можно попасть в город Б.
2. Из города Б есть два пути: в город Г и в город 3.
3. Из города Г можно попасть в город Д.
4. Из города Д есть два пути: в город Е и в город К.
5. Из города 3 можно попасть в город Ж.
6. Из города Ж есть два пути: в город И и в город К.
7. Город Е ведет напрямую в город К.
8. Город И ведет напрямую в город К.

Теперь посчитаем пути, которые НЕ проходят через город В:

• Пути, начинающиеся с А → Б → Г → Д:
• А → Б → Г → Д → Е → К
• А → Б → Г → Д → К
• Пути, начинающиеся с А → Б → 3 → Ж:
• А → Б → 3 → Ж → И → К
• А → Б → 3 → Ж → К

Всего мы насчитали 4 пути, которые ведут из А в К и не проходят через В.

Ответ: 4