Решение задачи: Найти количество путей из А в Л через Е

Вот решение задач, оформленное так, чтобы было удобно переписать в тетрадь школьнику. Задача 4: На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Е? Решение Задачи 4: Для решения этой задачи мы разделим путь на две части: 1. Пути из города А в город Е. 2. Пути из города Е в город Л. Затем перемножим количество путей в каждой части. Часть 1: Пути из города А в город Е. Будем подсчитывать количество путей до каждого города, начиная от А. * \(N_A = 1\) (начальный город) * \(N_Б = N_A = 1\) (путь А -> Б) * \(N_В = N_A = 1\) (путь А -> В) * \(N_Г = N_A = 1\) (путь А -> Г) * \(N_Д = N_Г = 1\) (путь Г -> Д) * \(N_Е = N_Б + N_В + N_Г = 1 + 1 + 1 = 3\) (пути Б -> Е, В -> Е, Г -> Е) Итак, существует 3 пути из города А в город Е. Часть 2: Пути из города Е в город Л. Теперь подсчитаем количество путей из Е в Л. * \(N_Е = 1\) (теперь Е - наш начальный город для этой части) * \(N_И = N_Е = 1\) (путь Е -> И) * \(N_З = N_Е = 1\) (путь Е -> З) * \(N_Ж = N_Д = 1\) (путь Д -> Ж, но Д не связан с Е напрямую, поэтому этот путь не учитывается в части Е -> Л, если только Д не был посещен до Е. Однако, по условию, мы ищем пути *через* Е, то есть Е должен быть промежуточным пунктом. Поэтому мы рассматриваем только пути, начинающиеся из Е.) * Важно: Если путь из А в Е прошел через Д, то Д уже посещен. Но в данном случае, мы считаем пути *из* Е. * Пути из Е: * Е -> И * Е -> З * Е -> Л (прямой путь) * \(N_Л = N_Е + N_И + N_З\) (пути Е -> Л, И -> Л, З -> Л) * \(N_Л = 1 + 1 + 1 = 3\) Итак, существует 3 пути из города Е в город Л. Общее количество путей из А в Л, проходящих через Е, равно произведению количества путей из А в Е и количества путей из Е в Л. Общее количество путей = \(N_{A \to E} \times N_{E \to Л} = 3 \times 3 = 9\). Ответ: 9 Задача 5: На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H, не проходящих через город D? Решение Задачи 5: Для решения этой задачи мы сначала найдем общее количество путей из A в H, а затем вычтем из них количество путей, проходящих через город D. 1. Общее количество путей из A в H: * \(N_A = 1\) * \(N_B = N_A = 1\) * \(N_C = N_A + N_B = 1 + 1 = 2\) (пути A -> C, B -> C) * \(N_D = N_A = 1\) * \(N_E = N_C = 2\) * \(N_F = N_C + N_D = 2 + 1 = 3\) * \(N_G = N_E + N_F = 2 + 3 = 5\) * \(N_H = N_G = 5\) Общее количество путей из A в H равно 5. 2. Количество путей из A в H, проходящих через город D: Для этого мы найдем количество путей из A в D, а затем количество путей из D в H, и перемножим их. * Пути из A в D: * \(N_A = 1\) * \(N_D = N_A = 1\) Итак, 1 путь из A в D (A -> D). * Пути из D в H: * \(N_D = 1\) (теперь D - наш начальный город для этой части) * \(N_F = N_D = 1\) (путь D -> F) * \(N_G = N_F = 1\) (путь F -> G) * \(N_H = N_G = 1\) (путь G -> H) Итак, 1 путь из D в H (D -> F -> G -> H). Количество путей из A в H, проходящих через D = \(N_{A \to D} \times N_{D \to H} = 1 \times 1 = 1\). Этот путь: A -> D -> F -> G -> H. 3. Количество путей из A в H, не проходящих через город D: Вычтем из общего количества путей те, что проходят через D. \(N_{A \to H \text{ (без D)}} = N_{A \to H \text{ (общие)}} - N_{A \to H \text{ (через D)}}\) \(N_{A \to H \text{ (без D)}} = 5 - 1 = 4\) Ответ: 4