На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Е и при этом не проходящих через пункт Л?
Количество путей до города П равно количеству путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения найдём последовательно количество путей до каждого из городов:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 1 + 1 + 1 = 3
Д = Б + Г = 4
Е = Г + Д = 7
И = Е = 7 (Г не учитываем, так как путь должен проходить через Е)
К = Е + И = 14
М = К = 14
П = М = 14
Приведем другое решение.
Количество путей из города А в город П, проходящих через город Е, равно произведению количества путей из города А в город Е и количества путей из города Е в город П. При этом, согласно условию задачи, путь из города Е в город П не должен проходить через город Л.
Найдем количество путей из города А в город Е:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 1 + 1 + 1 = 3
Д = Б + Г = 4
Е = Г + Д = 7.
Найдем количество путей из города Е в город П, не проходящих через город Л (при этом Е - исходный пункт):
Е = 1
И = Е = 1
К = Е + И = 2
М = К = 2
П = М = 2
Тогда количество путей из города А в город П, проходящих через Е, но не проходящих через Л, равно 7 · 2 = 14.
Ответ: 14.