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

Решение:

Будем считать количество путей, ведущих в каждый город, начиная с города А.

А: 1 путь (начальная точка).

Б: 1 путь (из А).

Г: 1 путь (из А).

В: 1 путь (из Б).

Д: 2 пути (из Б и из Г).

Ж: 3 пути (из В (1), из Д (2)).

И: 2 пути (из Д).

Е: 2 пути (из В (1), из Ж (2)).

К: 5 путей (из Ж (3), из И (2)).

1. Пути к городу Б: А → Б (1 путь).
2. Пути к городу Г: А → Г (1 путь).
3. Пути к городу В: А → Б → В (1 путь).
4. Пути к городу Д: А → Б → Д (1 путь) и А → Г → Д (1 путь). Всего 2 пути.
5. Пути к городу Ж: А → Б → В → Ж (1 путь) и А → Б → Д → Ж (1 путь) и А → Г → Д → Ж (1 путь). Всего 3 пути.
6. Пути к городу И: А → Б → Д → И (1 путь) и А → Г → Д → И (1 путь). Всего 2 пути.
7. Пути к городу Е: А → Б → В → Е (1 путь) и А → Б → В → Ж → Е (1 путь). Всего 2 пути.
8. Пути к городу К: А → Б → В → Ж → К (1 путь), А → Б → Д → Ж → К (1 путь), А → Г → Д → Ж → К (1 путь), А → Б → Д → И → К (1 путь), А → Г → Д → И → К (1 путь). Всего 5 путей.

Ответ: 5