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

Решение:

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

1. Пункты, достижимые из А:

• A: 1 путь (начало)
• Б: 1 путь (из А)
• Г: 1 путь (из А)
• В: 1 путь (из Б)
• И: 1 путь (из Г)

2. Пункты, ведущие к Е:

• Д: Пути к Д идут из Б и Г. Однако, по схеме, движение из Г в Д не указано, только из Б в Д. Исходя из направлений стрелок:
• Д: 1 путь (из Б)
• Е: Пути к Е идут из Д и Ж. Движение из Д в Е есть. Движение из Ж в Е тоже есть.
• Пути к Ж идут из Б и Д. Исходя из направлений стрелок:
• Ж: 1 путь (из Д)
• Таким образом, для достижения Е, нам нужно пройти через пункты, из которых есть стрелка в Е.
• Пути к Е:
• Из Д: 1 путь (А -> Б -> Д -> Е)
• Из Ж: Для Ж, пути идут из Б и Д. Но направление из Д в Ж не показано. Только из Ж в Д. Давайте пересмотрим схему.
  Пересмотр схемы:
  A → Б
  A → Г
  Б → В
  Б → Д
  Б → Ж
  Г → И
  Д → Е
  Д → Ж
  Е → Л
  Ж → Д (обратное направление, но стрелка показывает Ж->Д, не Д->Ж. Это значит, что из Д в Ж двигаться нельзя, только из Ж в Д. Это важно.)
  Ж → Е
  И → Л
  К → Л (пункт К не достижим из А)
  Л ← И, Л ← Е

Пересчет путей:

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

Окончательный расчет:

• A: 1
• Б: 1
• Г: 1
• В: 1 (из Б)
• Д: 1 (из Б)
• И: 1 (из Г)
• Ж: 1 (из Б)
• Е: (из Д) + (из Ж) = 1 + 1 = 2 пути.
• Л: (из И) + (из Е) = 1 + 2 = 3 пути.

Вопрос: Сколько существует различных путей из пункта А в пункт Л, проходящих через пункт Е?

Мы нашли, что в пункт Е ведет 2 пути из пункта А.

А → Б → Д → Е

А → Б → Ж → Е

Далее из Е мы идем в Л.

Значит, эти 2 пути, проходящие через Е, далее идут в Л.

Ответ: 2