На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Г или через пункт Л, но не через оба этих пункта?
[рис.]
[рис.]
💡 Пошаговый разбор и решение:
Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения найдём последовательно количество путей до каждого из городов, проходящих через пункт Г, но не проходящих через пункт Л:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 3
Д = Г = 3 (Б не учитываем, поскольку путь должен проходить через город Г)
Е = Д + Г = 6
Ж = Д = 3
И = Г + Е = 9
К = Е + И = 15
М = К = 15
Н = Ж = 3
П = Н + М = 18
Теперь найдём последовательно количество путей до каждого из городов, проходящих через пункт Л, но не проходящих через пункт Г:
А = 1
Б = А = 1
Д = Б = 1
Е = Д = 1
Ж = Д = 1
Л = Д + Е + Ж = 3
М = Л = 3
Н = Л = 3
П = Л + М + Н = 9
Таким образом, ответ — 18 + 9 = 27.
Ответ: 27.
Примечание.
В задаче требуется найти количество путей, которые либо проходят через пункт Г, но не проходят через пункт Л, либо проходят через пункт Л, но не проходит через пункт Г. Тем, у кого в результате решения данной задачи получается ответ, отличный от 27, рекомендуем проверить, все ли найденные пути удовлетворяют этим условиям.
При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения найдём последовательно количество путей до каждого из городов, проходящих через пункт Г, но не проходящих через пункт Л:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 3
Д = Г = 3 (Б не учитываем, поскольку путь должен проходить через город Г)
Е = Д + Г = 6
Ж = Д = 3
И = Г + Е = 9
К = Е + И = 15
М = К = 15
Н = Ж = 3
П = Н + М = 18
Теперь найдём последовательно количество путей до каждого из городов, проходящих через пункт Л, но не проходящих через пункт Г:
А = 1
Б = А = 1
Д = Б = 1
Е = Д = 1
Ж = Д = 1
Л = Д + Е + Ж = 3
М = Л = 3
Н = Л = 3
П = Л + М + Н = 9
Таким образом, ответ — 18 + 9 = 27.
Ответ: 27.
Примечание.
В задаче требуется найти количество путей, которые либо проходят через пункт Г, но не проходят через пункт Л, либо проходят через пункт Л, но не проходит через пункт Г. Тем, у кого в результате решения данной задачи получается ответ, отличный от 27, рекомендуем проверить, все ли найденные пути удовлетворяют этим условиям.
Правильный ответ:
27
📚 Похожие разобранные задания по предмету:
ID 31600 • Задание №11
В течение двух минут производилась четырёхканальная (квадро) звукозапись с частотой дискретизации 24 кГц и 16-...
ID 31191 • Задание №9
Для составления цепочек используются разные бусины, которые условно обозначаются цифрами 1, 2, 3, 4, 5. Каждая...
🔗 Другие задания линии №13 по предмету Информатика:
ID 31876
Маской подсети называется 32-разрядное двоичное число, которое определяет, какая часть IP-адр...
ID 31877
В терминологии сетей TCP/IP маской подсети называется 32-разрядное двоичное число, определяющ...
ID 31878
В терминологии сетей TCP/IP маской подсети называется 32-разрядное двоичное число, определяющ...
ID 31879
Если маска подсети 255.255.252.0 и IP-адрес компьютера в сети 226.185.90.162, то номер компьют...
ID 31880
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть I...