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

Решение:

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

Обозначим количество путей из города А в указанный город как N(город).

1. N(А) = 1 (точка старта).
2. N(Б) = N(А) = 1 (единственный путь из А).
3. N(Г) = N(А) = 1 (единственный путь из А).
4. N(В) = N(Б) + N(Г) = 1 + 1 = 2 (пути из Б и Г).
5. N(Д) = N(Г) = 1 (единственный путь из Г).
6. N(Е) = N(Б) = 1 (единственный путь из Б).
7. N(Ж): К городу Ж ведут дороги из В и Е. N(Ж) = N(В) + N(Е) = 2 + 1 = 3.
8. N(3) = N(Д) = 1 (единственный путь из Д).
9. N(И) = N(Ж) = 3 (путь из Ж, так как нам нужно пройти через Ж).
10. N(Л) = N(И) = 3 (путь из И).
11. N(М): К городу М ведут дороги из И и Л. N(М) = N(И) + N(Л) = 3 + 3 = 6.

Однако, условие задачи требует, чтобы пути проходили через город Ж, но НЕ проходили через город К.

Рассмотрим пути, ведущие к Ж:

• Из А в Ж, проходя через В: А → Б → В → Ж (1 путь)
• Из А в Ж, проходя через Г: А → Г → В → Ж (1 путь)
• Из А в Ж, проходя через Е: А → Б → Е → Ж (1 путь)

Таким образом, есть 3 пути до Ж.

Теперь рассмотрим пути из Ж в М, НЕ проходя через К:

• Путь из Ж в И, затем в Л, затем в М: Ж → И → Л → М. Количество таких путей: 3 (так как N(Ж)=3, то N(И)=3, N(Л)=3).

Поскольку мы должны пройти через Ж, и количество путей до Ж равно 3, и количество путей от Ж до М (не через К) равно 3:

\[ \text{Общее количество путей} = N(\text{пути до Ж}) \times N(\text{пути от Ж до М, без К}) \]

Пути до Ж:

• А→Б→В→Ж: 1 путь
• А→Г→В→Ж: 1 путь
• А→Б→Е→Ж: 1 путь

Всего 3 пути до Ж.

Пути из Ж до М, не через К:

• Ж → И → Л → М

Количество путей из Ж в М через И и Л:

• N(И) = N(Ж) = 3
• N(Л) = N(И) = 3
• N(М) = N(Л) = 3

Итак, количество путей из города А в город М, проходящих через город Ж, но не проходящих через город К, равно произведению количества путей до Ж и количества путей от Ж до М (минуя К).

Количество путей из А в Ж = 3.

Количество путей из Ж в М (через И, Л) = 3.

\[ \text{Итого} = 3 \times 3 = 9 \]

Ответ: 9.