Question

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По
каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. Сколько существует различных путей из города А в город К?

Answer 1

Ответ: 12

Каждой вершине, начиная с начальной (A), поставим индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь).

Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

Индекс В равен 2 (предков у В два – вершина A и вершина Б; 1 + 1 = 2).

И т.д.