Что именно надо посчитать
Кружки — города, стрелки — дороги. По дороге можно ехать только по стрелке. Путь — последовательность дорог от начального города до конечного. В этом задании мы не ищем длину маршрута: нужно узнать, сколько разных путей существует.
Рядом с начальным городом пишем 1: есть ровно один способ начать в нём. Если в другой город входят стрелки из нескольких городов, складываем числа у их начала. Каждый такой путь продолжается по своей стрелке и даёт один новый путь.
Когда дороги нужно исключить
| Что написано в задаче | Какие дороги оставляем |
|---|---|
| Никаких дополнительных условий | Все дороги по направлению стрелок. |
| «Обязательно через X» | Исключаем переходы, по которым можно добраться до финиша, уже миновав X. Не убираем пути, которые ещё могут войти в X. |
| «Не через E» | Удаляем E и все дороги, входящие в него или выходящие из него. |
| «Через X, но не через E» | Сначала удаляем E, затем обходы X. |
После этого снова ставим 1 в начале и складываем числа входящих путей. В каждом разборе ниже сначала показана исходная схема, а затем схема подсчёта с оставшимися дорогами.
Четыре схемы и подробные решения
1. Сколько путей из A в D
Условие. Сколько существует путей из города A в город D по указанным стрелками дорогам? По каждой дороге можно двигаться только в направлении стрелки.
Учитываем условие: Без дополнительных условий: считаем все разрешённые пути.
Начинаем с A: до старта есть один способ добраться — уже находиться в A. Каждая стрелка продлевает все пути из её начала на одну дорогу.
| Город | Откуда приходят пути | Итого |
|---|---|---|
| A | начальный город | 1 |
| B | из A | 1 |
| G | из A | 1 |
| E | из A, B и G: 1 + 1 + 1 | 3 |
| C | из B и E: 1 + 3 | 4 |
| H | из G и E: 1 + 3 | 4 |
| F | из E и H: 3 + 4 | 7 |
| D | из C, E и F: 4 + 3 + 7 | 14 |
Например, число 3 у E не взялось из количества дорог: это три разных способа прийти в E — напрямую из A, через B и через G. До D входят три стрелки, поэтому 4 + 3 + 7 = 14.
Ответ: 14.2. Из A в И обязательно через В
Условие. Сколько путей ведёт из A в И и при этом проходит через город В? По каждой дороге можно двигаться только в направлении стрелки.
Учитываем условие: Обязательный город В. Дороги Б → Е, Д → З и Г → З позволяют уйти к И мимо В: вычёркиваем их.
Сначала не считаем числа, а проверяем дороги. После удаления трёх обходов в городах Е и З уже нельзя оказаться без В. Теперь применяем обычное сложение входящих путей.
| Город | Откуда приходят пути | Итого |
|---|---|---|
| A | начальный город | 1 |
| Б | из A | 1 |
| Д | из A | 1 |
| Г | из A и Д: 1 + 1 | 2 |
| В | из A, Б и Г: 1 + 1 + 2 | 4 |
| Е | только из В | 4 |
| З | только из В | 4 |
| Ж | из В, Е и З: 4 + 4 + 4 | 12 |
| И | из Е, Ж и З: 4 + 12 + 4 | 20 |
Число 4 у В — четыре способа добраться до обязательного города. После него маршруты расходятся по Е, З и Ж. В И приходят 4 + 12 + 4 = 20 путей, и каждый уже прошёл через В.
Ответ: 20.3. Через Л, но не через Е
Условие. Сколько путей из A в М проходят через Л и не проходят через Е? По каждой дороге можно двигаться только в направлении стрелки.
Учитываем условие: Е запрещён: удаляем его и все связанные с ним дороги. Переход И → К → М обходит обязательный Л: его тоже исключаем.
Здесь два ограничения. Первым убираем Е со всеми дорогами, поэтому никакой путь на оставшейся схеме не нарушит запрет. Потом убираем ветку через К, по которой можно было достичь М без Л.
| Город | Откуда приходят пути | Итого |
|---|---|---|
| A | начальный город | 1 |
| Б | из A | 1 |
| Д | из A | 1 |
| Г | из A и Д: 1 + 1 | 2 |
| В | из A, Б и Г: 1 + 1 + 2 | 4 |
| З | из Д, Г и В: 1 + 2 + 4 | 7 |
| Ж | из В и З: 4 + 7 | 11 |
| И | из Ж и З: 11 + 7 | 18 |
| Л | только из И | 18 |
| М | только из Л | 18 |
Почему у М тоже 18? После удаления обхода через К в М осталась единственная входящая дорога из Л. Каждому из 18 путей до Л соответствует ровно один путь до М.
Ответ: 18.4. Из A в П обязательно через М
Условие. Сколько путей ведёт из A в П и обязательно проходит через М? По каждой дороге можно двигаться только в направлении стрелки.
Учитываем условие: Удаляем ветку через К и дорогу Ж → Л: они приводят к П без М. Дороги М → П и М → Л → П остаются.
После удаления обходов до П можно попасть только из М напрямую или из Л, но Л теперь достижим только из М. Значит любой оставшийся маршрут выполнит условие.
| Город | Откуда приходят пути | Итого |
|---|---|---|
| A | начальный город | 1 |
| Б | из A | 1 |
| Д | из A | 1 |
| Г | из A и Б: 1 + 1 | 2 |
| В | из Б и Г: 1 + 2 | 3 |
| Е | из Д и Г: 1 + 2 | 3 |
| Ж | из Г, В и Е: 2 + 3 + 3 | 8 |
| Н | из Д и Ж: 1 + 8 | 9 |
| М | из Ж и Н: 8 + 9 | 17 |
| Л | только из М | 17 |
| П | из М и Л: 17 + 17 | 34 |
До М есть 17 путей. Каждый можно закончить двумя разрешёнными способами: М → П или М → Л → П. Поэтому в П приходят 17 + 17 = 34 пути.
Ответ: 34.Как проверить свой подсчёт
- Выпиши требование задачи: все пути, через заданный город, без города или оба условия.
- Сначала исключи запрещённые переходы. После этого проверь, что каждый оставшийся маршрут действительно подходит.
- Поставь 1 у старта и считай города в порядке стрелок. Для каждого города назови все оставшиеся входящие стрелки и сложи числа у их начала.
- Проверь финиш: посчитай число путей по каждой входящей дороге и сложи. Не считай просто количество стрелок — по каждой может приходить несколько путей.
Четыре задачи с проверкой
Дороги перечислены стрелками. После ошибки можно исправить ответ и отправить его снова.
Решено: 0 из 4
1. Без дополнительных условий
Дороги: A → B, A → C, B → D, B → E, C → D, D → F, E → F. Сколько путей из A в F?
2. Обязательно через C
Дороги: A → B, A → C, B → C, B → D, C → D, C → E, D → F, E → F. Сколько путей из A в F проходят через C?
3. Не через E
Дороги: A → B, A → C, B → D, B → E, C → D, C → E, D → F, E → F. Сколько путей из A в F не проходят через E?
4. Через D, но не через C
Дороги: A → B, A → C, A → D, B → D, B → E, C → D, C → E, D → E, D → F, E → F. Сколько путей из A в F проходят через D, но не через C?
Видео по заданию №9
Видео скоро выйдет.
Продолжи подготовку к ОГЭ
Теперь ты умеешь считать пути и проверять ограничения. Создай аккаунт, чтобы решать следующие задания и продолжать практику на сайте.
Создать бесплатный аккаунтЕсли число не совпало
Почему у старта стоит 1?
Это один способ начать маршрут в исходном городе. Он позволяет посчитать пути во все города, в которые выходит первая стрелка.
Почему нужно сложить числа у входящих городов?
Каждая входящая дорога даёт свою группу путей. Любой путь к городу приходит по одной из этих дорог.
Можно ли просто вычеркнуть обязательный город у других маршрутов?
Нужно исключить именно пути, по которым можно достигнуть финиша без обязательного города. Разборы 2 и 4 показывают, какие переходы в исходных схемах дают такой обход.
Если хочешь повторить предыдущую тему, открой задание №8 про поисковые запросы.