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

Решение:

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

Шаг 1: Определяем количество путей из пункта А в каждый последующий пункт, избегая Е.

• А: 1 (исходная точка)
• Б: Из А в Б ведет 1 стрелка. Путь: А → Б. Количество путей: 1.
• Г: Из А в Г ведет 1 стрелка. Путь: А → Г. Количество путей: 1.
• В: Из А в В ведет 1 стрелка. Путь: А → В. Количество путей: 1.
• Д: Из Б в Д и из В в Д. Пути: А → Б → Д; А → В → Д. Количество путей: 1 (из А→Б) + 1 (из А→В) = 2.
• Ж: Из Д в Ж. Путь: А → Б → Д → Ж; А → В → Д → Ж. Количество путей: 2.
• Е: Из Д в Е и из Ж в Е. Мы не проходим через Е, поэтому этот пункт и исходящие из него пути игнорируем.
• И: Из Г в И и из Е в И. Поскольку Е пропускается, рассматриваем только пути через Г. Путь: А → Г → И. Количество путей: 1.
• К: Из Е в К и из Ж в К и из И в К.

Шаг 2: Пересчитываем пути к К, исключая Е.

Пункты, ведущие к К, это Ж, И, Е.

Мы не можем проходить через Е, поэтому пути через Е в К не учитываем.

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

• Пути из Ж в К: Мы уже выяснили, что в Ж ведут 2 пути (А → Б → Д → Ж и А → В → Д → Ж). От Ж до К есть одна стрелка. Таким образом, количество путей через Ж в К = 2.
• Пути из И в К: Мы выяснили, что в И ведет 1 путь (А → Г → И). От И до К есть одна стрелка. Таким образом, количество путей через И в К = 1.

Шаг 3: Суммируем пути к К.

Общее количество путей из А в К, не проходящих через Е, равно сумме путей через Ж и И:

Количество путей = (Пути через Ж) + (Пути через И)

Количество путей = 2 + 1 = 3.

Финальный ответ:

3