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

Решение:

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

• Город А: 1 путь (исходная точка)
• Город Б: 1 путь (из А)
• Город В: 1 путь (из А)
• Город Г: 1 путь (из А)
• Город Д: 1 путь (из А)
• Город Е: Пути из А в Е = Пути в Б + Пути в В = 1 + 1 = 2
• Город Ж: Пути из А в Ж = Пути в Е = 2
• Город З: Пути из А в З = Пути в Д = 1
• Город И: Пути из А в И = Пути в Е + Пути в Ж = 2 + 2 = 4
• Город К: Пути из А в К = Пути в З + Пути в Ж = 1 + 2 = 3
• Город Л: Пути из А в Л = Пути в И + Пути в К = 4 + 3 = 7

Однако, глядя на предложенные варианты ответов, моя первоначальная интерпретация схемы дорог могла быть неверной, или же я неправильно интерпретировал схему. Попробуем посчитать иначе, следуя логике графа.

Пересчет с учетом всех входящих дорог:

• А: 1
• Б: 1 (из А)
• В: 1 (из А)
• Г: 1 (из А)
• Д: 1 (из А)
• Е: (А->Б->Е) + (А->В->Е) = 1 + 1 = 2
• Ж: (А->Б->Е->Ж) + (А->В->Е->Ж) = 2
• З: (А->Д->З) = 1
• И: (А->Б->Е->Ж->И) + (А->В->Е->Ж->И) + (А->Б->Е->И) + (А->В->Е->И) = 2 + 2 = 4
• К: (А->Д->З->К) + (А->Б->Е->Ж->К) + (А->В->Е->Ж->К) = 1 + 2 = 3
• Л: (А->Б->Е->Ж->И->Л) + (А->В->Е->Ж->И->Л) + (А->Б->Е->И->Л) + (А->В->Е->И->Л) + (А->Д->З->К->Л) + (А->Б->Е->Ж->К->Л) + (А->В->Е->Ж->К->Л) = 4 + 3 = 7

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

Пути из А в Л:

• А -> Б -> Е -> И -> Л
• А -> Б -> Е -> Ж -> И -> Л
• А -> Б -> Е -> Ж -> К -> Л
• А -> В -> Е -> И -> Л
• А -> В -> Е -> Ж -> И -> Л
• А -> В -> Е -> Ж -> К -> Л
• А -> Г -> Е -> И -> Л
• А -> Г -> Е -> Ж -> И -> Л
• А -> Г -> Е -> Ж -> К -> Л
• А -> Д -> З -> К -> Л

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

• А: 1
• Б: 1 (из А)
• В: 1 (из А)
• Г: 1 (из А)
• Д: 1 (из А)
• Е: Пути к Е = Пути(А->Б->Е) + Пути(А->В->Е) + Пути(А->Г->Е) = 1 + 1 + 1 = 3
• Ж: Пути к Ж = Пути(А->Б->Е->Ж) + Пути(А->В->Е->Ж) + Пути(А->Г->Е->Ж) = 3
• З: Пути к З = Пути(А->Д->З) = 1
• И: Пути к И = Пути(А->Б->Е->И) + Пути(А->В->Е->И) + Пути(А->Г->Е->И) + Пути(А->Б->Е->Ж->И) + Пути(А->В->Е->Ж->И) + Пути(А->Г->Е->Ж->И) = 3 + 3 = 6
• К: Пути к К = Пути(А->Д->З->К) + Пути(А->Б->Е->Ж->К) + Пути(А->В->Е->Ж->К) + Пути(А->Г->Е->Ж->К) = 1 + 3 = 4
• Л: Пути к Л = Пути(А->...->И->Л) + Пути(А->...->К->Л) = 6 + 4 = 10

Я все еще не получил ни одного из предложенных вариантов. Пересмотрим схему и варианты.

Варианты: 15, 16, 17, 18.

Давайте попробуем пересчитать, более внимательно следуя стрелкам.

• А: 1
• Б: 1 (из А)
• В: 1 (из А)
• Г: 1 (из А)
• Д: 1 (из А)
• Е: Пути к Е = Пути(Б) + Пути(В) + Пути(Г) = 1 + 1 + 1 = 3
• Ж: Пути к Ж = Пути(Е) = 3
• З: Пути к З = Пути(Д) = 1
• И: Пути к И = Пути(Е) + Пути(Ж) = 3 + 3 = 6
• К: Пути к К = Пути(З) + Пути(Ж) = 1 + 3 = 4
• Л: Пути к Л = Пути(И) + Пути(К) = 6 + 4 = 10

Все еще 10. Возможно, на схеме города обозначены не так, как я предполагаю.

Посмотрим на варианты ответов: 15, 16, 17, 18. Мои расчеты показывают 10. Это означает, что я либо неправильно понимаю схему, либо не учитываю какие-то пути.

Давайте предположим, что есть еще один путь из А.

Пересчет с учетом всех возможных путей:

• А: 1
• Б: 1 (из А)
• В: 1 (из А)
• Г: 1 (из А)
• Д: 1 (из А)
• Е: Пути к Е = Пути(Б) + Пути(В) + Пути(Г) = 1 + 1 + 1 = 3
• Ж: Пути к Ж = Пути(Е) = 3
• З: Пути к З = Пути(Д) = 1
• И: Пути к И = Пути(Е) + Пути(Ж) = 3 + 3 = 6
• К: Пути к К = Пути(З) + Пути(Ж) = 1 + 3 = 4
• Л: Пути к Л = Пути(И) + Пути(К) = 6 + 4 = 10

Я постоянно прихожу к 10. Возможно, один из городов на схеме является началом пути, а не А. Но условие четко говорит