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

Решение:

Будем считать количество путей, ведущих в каждый пункт, начиная с пункта А, и отдельно пути, проходящие через И.

A: 1 путь

Б: 1 путь (из A)

Г: 1 путь (из A)

В: 1 путь (из A)

И: 3 пути (из Г; из Б -> Г -> И; из В -> И)

Ж: 1 путь (из И)

Д: 2 пути (из И; из Б -> И -> Д)

К: 2 пути (из И; из Д -> К)

Л: Пути в Л идут из И, Ж, К.

• Пути из И: 1 путь (из A -> Г -> И -> Л; из A -> Б -> Г -> И -> Л; из A -> В -> И -> Л)
• Пути из Ж: 1 путь (из A -> Г -> И -> Ж -> Л)
• Пути из К: 2 пути (из A -> Г -> И -> Д -> К -> Л; из A -> В -> И -> Д -> К -> Л)

Сначала посчитаем общее количество путей из А в Л.

A: 1

Б: 1

Г: 1

В: 1

И: 1 (из Г) + 1 (из Б->Г->И) + 1 (из В->И) = 3

Ж: 3 (из И)

Д: 3 (из И) + 1 (из Б->И->Д) = 4

К: 3 (из И) + 4 (из Д->К) = 7

Л: 3 (из И) + 3 (из Ж) + 7 (из К) = 13

Теперь посчитаем пути из А в Л, проходящие через И.

Число путей из А в И = 3.

Число путей из И в Л = 1 (из И->Л) + 1 (из И->Ж->Л) + 2 (из И->Д->К->Л) = 4.

Общее число путей из А в Л через И = (Пути из А в И) * (Пути из И в Л) = 3 * 4 = 12.

Ответ: 12