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

Решение:

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

1. Подсчет путей к пункту А: Из пункта А можно начать путь. Количество путей, ведущих в А, равно 1 (сам старт).
2. Подсчет путей к пункту Б: Из А можно попасть в Б. Количество путей в Б = пути в А = 1.
3. Подсчет путей к пункту Г: Из А можно попасть в Г. Количество путей в Г = пути в А = 1.
4. Подсчет путей к пункту В: Из Б можно попасть в В. Количество путей в В = пути в Б = 1.
5. Подсчет путей к пункту Д: Из Б и из Г можно попасть в Д. Количество путей в Д = пути в Б + пути в Г = 1 + 1 = 2.
6. Подсчет путей к пункту Ж: Из Д можно попасть в Ж. Количество путей в Ж = пути в Д = 2.
7. Учет условия: НЕ проходящих через пункт Е.
   • Путь А → Б → В → ...
   • Путь А → Г → ...
   • Путь А → Б → Д → Ж (2 пути)

   Теперь рассмотрим пути, которые могли бы пройти через Е:

   • Путь из А в Е: из В в Е, из Д в Е.
   • Путь из Е в Ж: из Е в Ж.

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

   Рассмотрим все пути из А в Ж:

   • A → Б → Д → Ж (2 пути, не проходят через Е)

   Путь через Е был бы, например, А → В → Е → Ж, но Е не ведет напрямую в Ж.

   Давайте пересчитаем, отталкиваясь от конечной точки Ж и двигаясь назад, или от начальной А, строго избегая Е.

   Пути из А, не проходящие через Е:

   • A → Б → Д → Ж (2 пути)

   Важно убедиться, что никакие другие пути не пересекают Е.

   Рассмотрим все возможные пути из А в Ж:

   • A → Б → Д → Ж
   • A → Г → Д → Ж

   Оба этих пути не используют пункт Е. Следовательно, количество таких путей равно 2.

Ответ: 2