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

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

Возможные пути:

1. A → B → F → G → M
2. A → B → F → H → M
3. A → C → F → G → M
4. A → C → F → H → M
5. A → D → F → G → M
6. A → D → F → H → M
7. A → E → F → G → M
8. A → E → F → H → M
9. A → F → G → M
10. A → F → H → M
11. A → D → F → K → M
12. A → D → E → L → K → M

Теперь посчитаем количество путей:

• A → B → F → K → M (Нет пути)
• A → B → F → L → K → M (Нет пути)
• A → C → F → K → M (Нет пути)
• A → C → F → L → K → M (Нет пути)
• A → D → F → K → M (Есть путь, нужно его добавить)
• A → D → F → L → K → M (Нет пути)
• A → E → F → K → M (Нет пути)
• A → E → F → L → K → M (Нет пути)
• A → F → K → M (Нет пути)
• A → F → L → K → M (Нет пути)

Исходя из схемы, можно выделить следующие пути:

1. A → B → F → G → M
2. A → B → F → H → M
3. A → C → F → G → M
4. A → C → F → H → M
5. A → D → F → G → M
6. A → D → F → H → M
7. A → E → F → G → M
8. A → E → F → H → M
9. A → F → G → M
10. A → F → H → M
11. A → D → F → K → M

Добавим ещё варианты: A → D → E → L → K → M

1. A → D → F → K → M
2. A → E → L → K → M - это один путь
3. Путь A → D → E → L → K → M - это один путь.

Теперь считаем пути по другому. Пути через F: A-F = 5 путей(A, B, C, D, E), следовательно из F в M ведут 3 пути(G, H, K, L), считаем: 5 * 3 = 15 путей, но через L только 1 путь, через K-1, а через G, H -2 = Итого 15 путей

Другие пути A->D->E->L->K->M, только тут надо смотреть, можно ли в E попасть D или нет.

Итого получаем: 11 путей.

Ответ: 11