Сколько существует различных путей из города А в город К, проходящих через город Г?

Решение:

Рассмотрим схему переездов между городами. Нам нужно найти все пути из города А в город К, которые обязательно проходят через город Г.

Путь из А в Г:

• А → Б → Г
• А → Г

Путь из Г в К:

• Г → Е → К
• Г → Д → Е → К
• Г → Ж → К
• Г → Д → Ж → К

Теперь соединим пути из А в Г с путями из Г в К:

1. (А → Б → Г) → (Г → Е → К) = А → Б → Г → Е → К
2. (А → Б → Г) → (Г → Д → Е → К) = А → Б → Г → Д → Е → К
3. (А → Б → Г) → (Г → Ж → К) = А → Б → Г → Ж → К
4. (А → Б → Г) → (Г → Д → Ж → К) = А → Б → Г → Д → Ж → К
5. (А → Г) → (Г → Е → К) = А → Г → Е → К
6. (А → Г) → (Г → Д → Е → К) = А → Г → Д → Е → К
7. (А → Г) → (Г → Ж → К) = А → Г → Ж → К
8. (А → Г) → (Г → Д → Ж → К) = А → Г → Д → Ж → К

Всего получилось 8 различных путей.

Ответ: 8.