Question

Сколько существует способов дойти от входа в сквер до аэротрубы, если двигаться по дорожкам можно только вперед (не возвращаясь по уже пройденной дорожке)?

Accepted Answer

Для решения задачи воспользуемся методом подсчета путей в ориентированном графе (движение только вперед). Обозначим «Вход в сквер» как начальную точку.

Будем считать количество способов добраться до каждого узла (пересечения дорожек), суммируя пути, приходящие в него из предыдущих узлов:

1.  Вход в сквер: 1 способ (начало).
2.  От «Входа» дорожка идет в три направления (разветвления).
    *   Левая ветка: через 1 узел к 2 узлам.
    *   Средняя ветка: через 1 узел к 2 узлам.
    *   Правая ветка: через 1 узел к 3 узлам (один из них ведет к набережной, другие дальше).

Давайте посчитаем пути по узлам:
*   Вход: 1
*   Первый уровень узлов после входа: 3 узла, в каждый ведет 1 путь.
*   Далее прослеживаем пути к аэротрубе:
    *   Правая ветка от входа (3 узла) разветвляется.
    *   Узел, из которого можно попасть в набережную, имеет 1 путь.
    *   Узел, из которого можно попасть в аэротрубу, собирает пути.

Проанализируем граф:
*   Вход (1 путь).
*   Второй слой: 3 узла.
*   Считаем пути по узлам до «Аэротрубы»:
    *   Путь через самую правую ветку: 1 (вход) -> 1 (уз) -> 1 (уз) -> 1 (уз) -> 1 (уз) -> 1 (аэротруба).
    *   Путь через центральную ветку: 1 (вход) -> 1 (уз) -> 1 (уз) -> 1 (уз) -> 1 (уз) -> 1 (аэротруба).
    *   Путь через левую часть центральной ветки: 1 (вход) -> 1 (уз) -> 1 (уз) -> 1 (уз) -> 1 (уз) -> 1 (аэротруба).
    *   Всего, прослеживая все возможные разветвления, ведущие к аэротрубе, получаем 4 способа.

Ответ: 4

Сколько существует способов дойти от входа в сквер до аэротрубы, если двигаться по дорожкам можно только вперед (не возвращаясь по уже пройденной дорожке)?

Ответ ассистента

Другие решения