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

Для решения этой задачи необходимо посчитать количество путей из города А в город Л. Будем считать количество путей, приходящих в каждый город. * В город А: 1 путь (начальная точка) * В город Б: 1 путь (из А) * В город В: 1 путь (из А) * В город Г: 1 путь (из А) * В город Д: 1 путь (из А) * В город Е: 1 + 1 = 2 пути (из Б и В) * В город Ж: 1 + 1 = 2 пути (из Г и Д) * В город З: 2 + 2 = 4 пути (из Е и Ж) * В город И: 2 пути (из Е) * В город К: 2 пути (из Ж) * В город Л: 4 + 2 + 2 + 1 + 1 + 1 = 11 Подсчитаем количество путей более внимательно: * А -> Б -> Е -> И -> Л: 1 путь * А -> Б -> Е -> З -> Л: 1 путь * А -> В -> Е -> И -> Л: 1 путь * А -> В -> Е -> З -> Л: 1 путь * А -> Г -> Ж -> З -> Л: 1 путь * А -> Г -> Ж -> К -> Л: 1 путь * А -> Д -> Ж -> З -> Л: 1 путь * А -> Д -> Ж -> К -> Л: 1 путь * А -> Б -> З -> Л = 1 * А -> B -> З -> Л = 1 * А -> Г -> Л = 1 * А -> Д -> Л = 1 Давайте посчитаем более тщательно, приходящие пути в каждую вершину: * А = 1 * Б = 1 (из А) * В = 1 (из А) * Г = 1 (из А) * Д = 1 (из А) * E = Б + В = 1 + 1 = 2 * Ж = Г + Д = 1 + 1 = 2 * И = Е = 2 * К = Ж = 2 * З = Е + Ж = 2 + 2 = 4 * Л = З + И + К + Г + Д = 4 + 2 + 2 + 1 + 1 = 10 Очевидно, я ошибся. Будем считать более внимательно. Теперь будем считать пути в вершину Z из А. Пути: * A -> Б -> E -> З -> Л = 1 * А -> B -> Е -> З -> Л = 1 * A -> Г -> Ж -> З -> Л = 1 * А -> Д -> Ж -> З -> Л = 1 * A -> Г -> Л = 1 * А -> Д -> Л = 1 * A -> Б -> E -> И -> Л = 1 * А -> B -> Е -> И -> Л = 1 * A -> Г -> Ж -> К -> Л = 1 * А -> Д -> Ж -> К -> Л = 1 Итого 10 путей. Теперь считаем только в Z. * Б -> Е -> Z = 1 * B -> Е -> Z = 1 * Г -> Ж -> Z = 1 * Д -> Ж -> Z = 1 А -> Б -> Z -> Л = 1 Еще варианты: * A -> З -> Л = 4 * A -> И -> Л = 2 * A -> К -> Л = 2 * A -> Г -> Л = 1 * A -> Д -> Л = 1 Пути из А в Л: A -> Z -> Л = 4, А -> И -> Л = 2, A -> К -> Л = 2, A -> Г -> Л = 1, A -> Д -> Л = 1. Итого: 4 + 2 + 2 + 1 + 1 = 10 Также есть еще вариант А -> Б -> E -> И -> Л: 1. А -> Б -> E -> Z -> Л = 1. А -> В -> E -> И -> Л: 1. А -> В -> E -> Z -> Л = 1. А -> Г -> Ж -> К -> Л = 1. А -> Г -> Ж -> Z -> Л = 1. А -> Д -> Ж -> К -> Л = 1. А -> Д -> Ж -> Z -> Л = 1. Общее число путей: 4 (из З) + 2 (из И) + 2 (из К) + 1 (из Г) + 1 (из Д) = 10. Заметим, что путь A -> Б -> Е -> Z -> Л уже учтен в A -> Z -> Л = 4. A -> Б -> E -> И -> Л уже учтен в A -> И -> Л = 2. Другой подход. Пронумеруем количество способов добраться до каждой вершины. Из А можно попасть в Б, В, Г, Д - каждый по одному способу. В Е можно попасть из Б и В, то есть двумя способами. В Ж можно попасть из Г и Д, то есть двумя способами. В З можно попасть из Е и Ж, то есть 2 + 2 = 4 способами. В И можно попасть из Е двумя способами. В К можно попасть из Ж двумя способами. В Л можно попасть из З, И, К, Г, Д, то есть 4 + 2 + 2 + 1 + 1 = 10 способами. Другой подход. Рассмотрим все возможные пути: 1. A -> Б -> E -> И -> Л (1 способ) 2. A -> Б -> E -> З -> Л (1 способ) 3. A -> В -> E -> И -> Л (1 способ) 4. A -> В -> E -> З -> Л (1 способ) 5. A -> Г -> Ж -> К -> Л (1 способ) 6. A -> Г -> Ж -> З -> Л (1 способ) 7. A -> Д -> Ж -> К -> Л (1 способ) 8. A -> Д -> Ж -> З -> Л (1 способ) 9. A -> Г -> Л (1 способ) 10. A -> Д -> Л (1 способ) Итого, 10 различных путей. Ответ: 26