Хорошо, давай попробуем решить номер 3 вместе.
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. Есть правило перемещения только в одном направлении, указанном стрелкой. Тебе нужно найти количество различных путей из города А в город Ж.
Для начала посчитаем, сколько есть путей от города А до каждого другого города, а из него в город Ж.
Из города А:
- 1 путь в город Б (через АБ)
- 1 путь в город В (через АВ)
Теперь посмотрим пути в город Г:
- Из города Б в город Г (через БГ)
- Из города В в город Г (через ВГ)
Так как в город Г можно попасть двумя способами (из городов Б и В), общее число путей до Г будет равно сумме путей до этих городов, т.е. 2 пути (1 через Б и 1 через В).
Аналогично для городов Д и Е:
- В город Д можно попасть из города Б (1 путь) и из города Г (2 пути), что в сумме даст 3 пути.
- В город Е можно попасть из города В (1 путь) и города Г (2 пути), всего также 3 пути.
Наконец считаем пути до города Ж:
- Из города Г в Ж только один путь, но до Г мы могли прийти двумя путями, значит умножаем 1 на 2, получаем 2 пути в Ж через Г.
- Из города Д тоже один путь в Ж, но до Д можно было добраться 3 путями, поэтому умножаем 1 на 3, получаем 3 пути в Ж через Д.
- Из города Е в Ж также один путь, и до Е - 3 пути, так что ещё 3 пути в Ж через Е.
Сложим все возможные пути в город Ж:
2 (через Г) + 3 (через Д) + 3 (через Е) = 8 путей из города А в город Ж.
Итак, существует 8 различных путей для попадания из города А в город Ж.
Комментарии