Реши задание на изображении
Краткий ответ: 9 путей. В поле записано 6 — это меньше правильного значения; проверка перебором ниже показывает, каких маршрутов не хватает.
Как считать: метод «число путей в вершину»
Пусть \(N(X)\) — число путей из А в город \(X\). Тогда
\[ N(X)=\sum N(Y) \quad \text{по всем городам } Y, \text{ из которых идёт стрелка } Y\to X . \]
Начинаем с \(N(\mathrm{А})=1\) (один пустой путь — стоять на месте) и идём по схеме в таком порядке, чтобы к моменту подсчёта все входящие стрелки были уже учтены: А → Б, Г → В → Д, Е → К.
| Город | Из каких городов ведут стрелки | Число путей |
|---|---|---|
| А | — (старт) | 1 |
| Б | А | 1 |
| Г | А | 1 |
| В | А, Б, Г | \(1+1+1=3\) |
| Д | Б | 1 |
| Е | В, Г | \(3+1=4\) |
| К | Б, В, Д, Е | \(1+3+1+4=9\) |
Главное здесь — не забыть, что каждый путь, попавший в В, дальше раздваивается: можно сразу в К, а можно через Е.
Проверка перебором всех маршрутов
Через Б (4 пути):
- А–Б–К
- А–Б–Д–К
- А–Б–В–К
- А–Б–В–Е–К
Сразу через В (2 пути): 5. А–В–К 6. А–В–Е–К
Через Г (3 пути): 7. А–Г–В–К 8. А–Г–В–Е–К 9. А–Г–Е–К
Итого \(4+2+3=9\) — совпадает с таблицей.
Где обычно теряются пути
Ответ 6 получается, если считать «по одной дороге от каждого города» и не учитывать, что после В есть два продолжения (В→К и В→Е→К), а пути, прошедшие через Г, тоже попадают в В и дальше снова раздваиваются. Поэтому надёжнее не перебирать вручную, а складывать числа путей по стрелкам — так ни одна ветка не потеряется.
