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

Решение:

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

1. Пути через город Д:

Чтобы добраться из А в К через Д, нам нужно пройти из А в Д, а затем из Д в К.

Пути из А в Д:

• А → Б → Г → Д
• А → Б → Д
• А → В → Г → Д
• А → В → Д

Всего 4 пути из А в Д.

Пути из Д в К:

• Д → Ж → К
• Д → Ж → З → К
• Д → Е → Ж → К
• Д → Е → Ж → З → К
• Д → Е → З → К

Сначала найдем пути из Д в К, проходящие только через Е:

• Д → Е → Ж → К
• Д → Е → Ж → З → К
• Д → Е → З → К

Теперь найдем пути из Д в К, не проходящие через Е:

• Д → Ж → К
• Д → Ж → З → К

Всего путей из Д в К: 3 (через Е) + 2 (не через Е) = 5 путей.

Общее количество путей из А в К через Д: 4 (пути А→Д) * 5 (пути Д→К) = 20 путей.

2. Пути через город Е:

Чтобы добраться из А в К через Е, нам нужно пройти из А в Е, а затем из Е в К.

Пути из А в Е:

• А → Б → Д → Е
• А → Б → Г → Д → Е
• А → В → Д → Е
• А → В → Г → Д → Е
• А → Б → Д → Ж → Е
• ... (и так далее, учитывая, что Д может вести к Е, а Ж может вести к Е)

Давайте посчитаем пути из А в Е более систематично, используя принцип сложения путей:

Количество путей из А в А: 1 (точка старта)

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

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

Количество путей из А в Г: А→Б→Г (1) + А→В→Г (1) = 2

Количество путей из А в Д: А→Б→Д (1) + А→В→Д (1) + А→Б→Г→Д (2) + А→В→Г→Д (2) = 1 + 1 + 2 + 2 = 6 (ошибочный подсчет, пересчитаем)

Пересчет путей из А в Д:

• А → Б → Д: 1
• А → В → Д: 1
• А → Б → Г → Д: 1
• А → В → Г → Д: 1
• Итого из А в Д = 4 пути (как было найдено ранее).

Пути из А в Е:

• Пути, ведущие в Д, а затем в Е: 4 (пути А→Д) * 1 (Д→Е) = 4 пути.
• Пути, ведущие в Ж, а затем в Е: (пути А→Ж) * 1 (Ж→Е).
• Пути из А в Ж: А→Б→Д→Ж (1), А→В→Д→Ж (1), А→Б→Г→Д→Ж (1), А→В→Г→Д→Ж (1), А→Б→Ж (1), А→В→Ж (1).
• Пути из А в Ж: 6 путей.
• Пути из А в Ж, ведущие в Е: 6 (пути А→Ж) * 1 (Ж→Е) = 6 путей.
• Общее количество путей из А в Е = 4 (через Д) + 6 (через Ж) = 10 путей.

Пути из Е в К:

• Е → Ж → К
• Е → Ж → З → К
• Е → З → К

Всего 3 пути из Е в К.

Общее количество путей из А в К через Е: 10 (пути А→Е) * 3 (пути Е→К) = 30 путей.

3. Пути через оба города (Д и Е):

Путь должен пройти через Д, а затем через Е (или наоборот, но схема не позволяет пройти из Е в Д). Значит, путь должен быть А → ... → Д → Е → ... → К.

Пути из А в Д: 4 пути (как найдено ранее).

Пути из Д в Е: 1 путь (Д → Е).

Пути из Е в К: 3 пути (как найдено ранее).

Общее количество путей из А в К через Д и затем через Е: 4 (А→Д) * 1 (Д→Е) * 3 (Е→К) = 12 путей.

4. Итоговое количество путей (через Д или Е):

Количество путей (через Д) + Количество путей (через Е) - Количество путей (через Д и Е)

20 + 30 - 12 = 38 путей.

Ответ: 38