На рисунке – схема дорог, связывающих города А, В, С, D, E, F, G и Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Н, проходящих через город С?

Решение:

Чтобы найти количество различных путей из города А в город Н, проходящих через город С, проследим все возможные пути, следуя стрелкам на схеме:

• Из города А можно попасть в города B и C.
• Пути, проходящие через C:
• A → C → E → H
• A → C → F → H
• A → C → G → H
• Пути, не проходящие через C, исключаются.
• Пути, начинающиеся с A → B, также не проходят через C:
• A → B → C → E → H
• A → B → C → F → H
• A → B → C → G → H

Таким образом, мы рассматриваем пути, где город С является обязательным пунктом следования. Из города А есть два пути, ведущих непосредственно в город C:

1. Путь через город B: A → B → C. Из города C далее можно попасть в E, F, G.
2. Путь напрямую в город C: A → C. Из города C далее можно попасть в E, F, G.

Рассмотрим пути из А в Н, проходящие через С:

1. A → C → E → H: 1 путь
2. A → C → F → H: 1 путь
3. A → C → G → H: 1 путь

Теперь рассмотрим пути, где мы сначала попадаем в B, затем в C:

1. A → B → C → E → H: 1 путь
2. A → B → C → F → H: 1 путь
3. A → B → C → G → H: 1 путь

Всего путей, проходящих через город С, равно сумме путей из A в C и далее в H, плюс пути из A в B, затем в C и далее в H.

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

• Напрямую: 1 (A → C)
• Через B: 1 (A → B → C)
• Всего из А в С: 1 + 1 = 2 пути.

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

• С → E → H: 1 путь
• С → F → H: 1 путь
• С → G → H: 1 путь
• Всего из С в Н: 1 + 1 + 1 = 3 пути.

Общее количество путей из А в Н через С = (количество путей из А в С) * (количество путей из С в Н)

Однако, мы должны считать непроизводные пути. Давайте посчитаем, сколько путей ведут из А в Н через С, учитывая все возможности:

Пути через C:

1. A → C → E → H
2. A → C → F → H
3. A → C → G → H

Теперь пути, где C является промежуточным пунктом, но не первым из A:

1. A → B → C → E → H
2. A → B → C → F → H
3. A → B → C → G → H

Каждый из этих путей уникален и проходит через C. Всего таких путей:

1 (A→C→E→H) + 1 (A→C→F→H) + 1 (A→C→G→H) + 1 (A→B→C→E→H) + 1 (A→B→C→F→H) + 1 (A→B→C→G→H) = 6 путей.

Ответ: 6.