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

Question

Вопрос:

Accepted Answer

Привет! Давай посчитаем все возможные пути из А в Л, которые обязательно проходят через И.

Из А можно попасть в Б.
Из Б можно попасть в Г.
Из Г можно попасть в Д.
Из Д можно попасть в Е.
Из Е можно попасть в Ж.
Из Ж можно попасть в И.
Путь 1: А -> Б -> Г -> Д -> Е -> Ж -> И
Теперь рассмотрим другие варианты:
Из А можно попасть в В.
Из В можно попасть в Г.
Из Г можно попасть в Д.
Из Д можно попасть в Е.
Из Е можно попасть в Ж.
Из Ж можно попасть в И.
Путь 2: А -> В -> Г -> Д -> Е -> Ж -> И
Из А можно попасть в Б.
Из Б можно попасть в В.
Из В можно попасть в Г.
Из Г можно попасть в Д.
Из Д можно попасть в Е.
Из Е можно попасть в Ж.
Из Ж можно попасть в И.
Путь 3: А -> Б -> В -> Г -> Д -> Е -> Ж -> И
Рассмотрим путь к Е напрямую из А, если такое возможно. На схеме видно, что из А можно попасть в В и Б. Из В в Г, из Б в Г. Из Г в Д. Из Д в Е.
Посмотрим на все пути, которые ведут к И:

Также есть пути, где И достигается через Л, но нам нужно попасть в Л через И, так что нас интересуют пути, где И является предпоследним пунктом перед Л.
Давай посчитаем количество путей к И более системно:

К А: 1 (начальная точка)
К Б: 1 (из А)
К В: 1 (из А)
К Г: 2 (из Б, из В)
К Д: 2 (из Г)
К Е: 4 (из Д, из В - но В ведет в Г, а Г в Д, поэтому из Д в Е = 2 пути; из Е также можно попасть в Л. Из Д можно попасть в Л. Из Е можно попасть в Ж.
Пересчитаем по-другому, чтобы избежать путаницы
Пути из А в И:

Ответ: 3