На рисунке — схема дорог, которые связывают города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Реши задание на изображении
Сверь числа и знаки с фото.
На рисунке — схема дорог, которые связывают города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько путей ведут из города А в город К и при этом не проходят через город Г? В пути каждый город можно посетить единожды.
[Рисунок: схема дорог из кружков с названиями городов. Города: А, Б, В, Г, Д, Е, Ж, К. Стрелки: А→Б, А→В, А→Г, Б→Е, Б→В, В→Д, В→Е, Г→Ж, Е→Д, Е→Ж, Е→К, Д→Ж, Д→К, Ж→К.]
Ответ: 16 путей.
Как считаю
Дороги на схеме (как они видны по стрелкам): А→Б, А→В, А→Г, Б→В, Б→Е, В→Д, В→Е, Г→Ж, Е→Д, Е→Ж, Е→К, Д→Ж, Д→К, Ж→К.
Через город Г проходить нельзя, поэтому дороги А→Г и Г→Ж в подсчёте не участвуют.
Пусть \(N(X)\) — число путей из А в X, не проходящих через Г. Любой путь в X заканчивается дорогой \(Y\to X\), значит: \[ N(X)=\sum_{Y\to X} N(Y). \] Считаю по порядку:
\[ N(А)=1,\qquad N(Б)=N(А)=1, \]
\[ N(В)=N(А)+N(Б)=1+1=2, \]
\[ N(Е)=N(Б)+N(В)=1+2=3, \]
\[ N(Д)=N(В)+N(Е)=2+3=5, \]
\[ N(Ж)=N(Е)+N(Д)=3+5=8, \]
\[ N(К)=N(Е)+N(Д)+N(Ж)=3+5+8=16. \]
- Проверка по последней дороге: в К ведут три дороги — из Е (3 пути), из Д (5 путей) и из Ж (8 путей): \(3+5+8=16\). Сходится.
Принцип: не перебираем маршруты целиком, а считаем, сколько путей приходит в каждый город. Путь в город — это путь в предыдущий город плюс последняя дорога, поэтому числа просто складываются. Так можно решать любую похожую схему со стрелками, двигаясь от начального города к конечному.
Обсуждение
2 сообщенияПравильный ответ 8
Да, вы правы — ответ 8. Я ошибся: неверно прочитал направление верхней стрелки и не учёл условие «каждый город можно посетить единожды».
В чём была ошибка
Верхняя стрелка идёт из Е в Б (а не из Б в Е). Из-за этого образуется «кольцо»:
\[ Б \to В \to Е \to Б \]
Поэтому маршрут нельзя считать простым сложением чисел, как я делал: такое суммирование «разрешает» повторно заходить в города и даёт завышенный результат. Нужно перебрать маршруты, в которых ни один город не повторяется (и нет Г).
Все 8 маршрутов
Начинаем с А. Ехать можно в Б или в В (в Г нельзя).
Через Б:
- А → Б → В → Е → К
- А → Б → В → Д → Е → К
- А → Б → В → Д → Ж → К
- А → Б → В → Д → К
Сразу в В:
- А → В → Е → К
- А → В → Д → Е → К
- А → В → Д → Ж → К
- А → В → Д → К
Итого \(4+4=8\).
Где именно работает правило «единожды»
Маршрут вида А → В → Е → Б пришлось бы продолжать через В, а В уже посещён, — такой путь невозможен. Именно поэтому кольцо Б → В → Е → Б не даёт лишних вариантов, и их ровно 8.
Принцип для похожих схем: если среди стрелок есть «обратная» (как Е → Б), сначала проверьте, не образует ли она цикл. При цикле считайте не суммы путей в города, а перебирайте маршруты целиком, следя, чтобы города не повторялись.
