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

Решение:

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

1. Из А:
• В Б: 1 путь
• В Г: 1 путь
2. В города, куда можно попасть из А:
• В В: Можно попасть только из Б. Путей в В = Путей в Б = 1.
3. В города, куда можно попасть из А и Б, В:
• В Е: Можно попасть из В. Путей в Е = Путей в В = 1.
4. В города, куда можно попасть из А, Б, Г:
• В Д: Можно попасть из Г. Путей в Д = Путей в Г = 1.
5. В города, куда можно попасть из А, Б, В, Г, Д, Е:
• В Ж: Можно попасть из В и Д. Путей в Ж = Путей в В + Путей в Д = 1 + 1 = 2.
• В З: Можно попасть из Е. Путей в З = Путей в Е = 1.
• В И: Можно попасть из Д. Путей в И = Путей в Д = 1.
6. В город К:
• В К: Можно попасть из Ж, З, И. Путей в К = Путей в Ж + Путей в З + Путей в И = 2 + 1 + 1 = 4.

Ответ: 4