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

Решение:

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

А: 1 путь (начало).

Б: 1 путь (из А).

Г: 1 путь (из А).

Д: 1 путь (из Г).

Е: 1 путь (из Б).

Ж: \( 1 (\text{из Е}) + 1 (\text{из Г}) = 2 \) пути.

В: \( 1 (\text{из А}) + 1 (\text{из Б}) = 2 \) пути.

К: \( 2 (\text{из Ж}) + 2 (\text{из В}) = 4 \) пути.

Л: \( 4 (\text{из К}) = 4 \) пути.

М: \( 4 (\text{из Л}) = 4 \) пути.

Н: \( 4 (\text{из К}) + 4 (\text{из М}) = 8 \) путей.

П: \( 2 (\text{из Ж}) + 4 (\text{из М}) = 6 \) путей.

Р: \( 6 (\text{из П}) = 6 \) путей.

С: \( 6 (\text{из Р}) = 6 \) путей.

Т: \( 6 (\text{из П}) + 6 (\text{из С}) = 12 \) путей.

Однако, условие задачи требует пройти через город Н. Поэтому мы должны учитывать только пути, которые ведут в Н, а затем в Т.

Пути, ведущие в Н, мы уже посчитали: 8 путей.

Из Н можно попасть в:

• П: \( 8 (\text{из Н}) \) пути.
• Т: \( 8 (\text{из Н}) \) пути (прямой путь из Н в Т, если он существует, но на схеме его нет, нужно проверить связи Н-П-Т).

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

Пути из А в Н: 8.

Из Н мы можем попасть в П. Количество путей из А в П, проходящих через Н: 8.

Из П мы можем попасть в Т. Количество путей из А в Т, проходящих через Н и П: 8.

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

На схеме видно, что из Н можно попасть в П, а из П - в Т. А также, что из Ж можно попасть в П. Давайте пересчитаем пути, учитывая, что нужно пройти через Н.

А: 1

Б: 1

Г: 1

Д: 1

Е: 1

Ж: \( 1(\text{из Е}) + 1(\text{из Г}) = 2 \)

В: \( 1(\text{из А}) + 1(\text{из Б}) = 2 \)

К: \( 2(\text{из Ж}) + 2(\text{из В}) = 4 \)

Л: \( 4(\text{из К}) = 4 \)

М: \( 4(\text{из Л}) = 4 \)

Н: \( 4(\text{из К}) + 4(\text{из М}) = 8 \)

Теперь считаем пути из Н в Т.

Из Н идем в П. Количество путей из А в Н = 8.

Пути А → ... → Н → П:

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

Из Н в П: 8 путей.

Из П в Т: 6 путей.

Количество путей А → ... → Н → П → Т = \( 8 \cdot 6 = 48 \). Однако, это неверный подход, так как это пути из А в Т через Н и П, а не просто через Н.

Нужно посчитать пути из А до Н, а затем из Н до Т, умножив количество путей.

Пути из А в Н = 8.

Теперь посчитаем пути из Н в Т:

Н: 1 (исходная точка для этого участка)

П: \( 8 (\text{из Н}) \) - это количество путей из А в П через Н.

М: \( 8 (\text{из Н}) \) - если бы была дорога Н-М, но ее нет.

Ж: \( 8 (\text{из Н}) \) - если бы была дорога Н-Ж, но ее нет.

К: \( 8 (\text{из Н}) \) - если бы была дорога Н-К, но ее нет.

Л: \( 8 (\text{из Н}) \) - если бы была дорога Н-Л, но ее нет.

Т: (пути из Н в Т)

Из Н можно попасть в П (8 путей).

Из П можно попасть в Т (6 путей).

Значит, из Н в Т через П: \( 8 \cdot 6 = 48 \) путей.

Однако, схема показывает, что П и Т связаны. Нужно пересчитать пути из Н до Т.

Н: 1

П: \( 1 \cdot \text{связи из Н в П} \). На схеме из Н есть стрелка в П. Значит, количество путей из А в Н = 8. Эти 8 путей ведут в Н. Из Н можно попасть в П. Значит, количество путей из А в П через Н = 8.

Т: Из П ведет стрелка в Т. Количество путей из А в Т через Н и П = \( 8 \times \text{число путей из П в Т} \).

Число путей из П в Т:

П: 1 (начало)

Т: 1 (из П)

С: \( 1 (\text{из Т}) \)

Это неверно. Нужно считать количество путей из города в город.

Количество путей из A в H = 8.

Теперь считаем количество путей из H в T:

H: 1 (точка старта)

П: 1 (из H в P)

T: 1 (из P в T)

Общее количество путей из A в T, проходящих через H:

Количество путей из A в H = 8.

Количество путей из H в T:

Из H мы можем попасть в P. Из P мы можем попасть в T. Таким образом, есть путь H → P → T.

Число путей из H в P = 1.

Число путей из P в T = 1.

Следовательно, число путей из H в T через P = \( 1 \times 1 = 1 \).

Общее количество путей из A в T, проходящих через H = (Количество путей из A в H) * (Количество путей из H в T)

Общее количество путей = \( 8 \times 1 = 8 \).

Ответ: 8.