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