На рисунке показана схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

Для решения схему дорог нужно развернуть.

Шаг 1. Из пункта А ведут пути в пункты B, D и C:

Шаг 2. Из пункта B пути ведут в пункты E и D:

Шаг 3. Из пункта E пути ведут в H и G, и из пункта G в H:

Обратите внимание, пункт H — конечный, и обведен красным кружком (для удобства, чтобы не запутаться).

Шаг 4. Из пункта D пути ведут в E, G и F

Шаг 5. Как мы знаем, из пункта E у нас 2 пути, из G — один путь, и из пункта F путь ведет в пункт G, из которого один путь:

Шаг 6. Теперь видно, что из пункта D ведут четыре пути, отметим это на графе для пункта D:

Шаг 7. Остаётся последняя ветвь — пункт С. Из него ведёт только один путь, в пункт D, из которого четыре пути:

Остаётся подсчитать общее количество путей. 1+1+2+1+1+4+4=14

Ответ: 14