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

Решение:

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

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

Б: 1 (из А)

Г: 1 (из А)

В: 1 (из Б)

Д: 2 (из А и из Б)

Е: 1 (из Г) + 1 (из В) + 2 (из Д) = 4

Ж: 4 (из Е)

З: 1 (из Ж)

И: 4 (из Е)

К: 1 (из Ж) + 1 (из И) = 2

Ответ: 2