39. Сколько имеется кратчайших путей, проходящих по рёбрам куба, из одной его вершины в противоположную?

Решение:

Куб имеет 8 вершин. Противоположная вершина находится на максимально возможном расстоянии от начальной. Чтобы добраться до противоположной вершины, нужно пройти как минимум 3 ребра. Рассмотрим, как можно попасть из одной вершины в противоположную, проходя ровно 3 ребра.

Пусть начальная вершина — A. Противоположная вершина — G.

Возможные кратчайшие пути (длиной 3 ребра):

1. A → B → C → G
2. A → B → H → G
3. A → D → C → G
4. A → D → E → G
5. A → E → F → G
6. A → E → H → G

Проверим, все ли эти пути действительно кратчайшие и ведут в противоположную вершину. Каждое ребро увеличивает расстояние на 1. Чтобы попасть в противоположную вершину, нужно пройти 3 ребра. Если пройти 4 ребра, то мы окажемся в соседней вершине, а если 5 — то в вершине, соседней с противоположной. Поэтому кратчайший путь — это 3 ребра.

Каждый путь соответствует выбору направления на каждом шаге. На первом шаге у нас 3 варианта ребра. На втором шаге, из каждой из этих вершин, у нас тоже 3 варианта ребра. И так далее. Однако, нам нужно попасть именно в противоположную вершину.

Пусть начальная вершина имеет координаты (0,0,0). Противоположная вершина будет (1,1,1) (если ребро равно 1).

Для достижения (1,1,1) из (0,0,0) нам нужно сделать 3 шага, каждый из которых изменяет одну координату.

На первом шаге мы можем выбрать любое из 3 ребер. Например, если мы двигаемся вдоль оси X, мы попадаем в (1,0,0).

На втором шаге мы можем выбрать ребро, ведущее вдоль оси Y, попадая в (1,1,0).

На третьем шаге мы можем выбрать ребро, ведущее вдоль оси Z, попадая в (1,1,1).

Таким образом, на каждом из 3 шагов у нас есть выбор ребра, которое ведет в нужном направлении (т.е. изменяет одну из оставшихся координат). На каждом шаге из 3 возможных ребер, одно ведет к цели (т.е. к противоположной вершине), а два других ведут к соседним вершинам.

Нет, это неверно. Давайте просто перечислим пути.

Из вершины A, мы можем пойти в B, D, E.

Если идем в B:

1. A→B→C→G
2. A→B→H→G

Если идем в D:

1. A→D→C→G
2. A→D→E→G

Если идем в E:

1. A→E→F→G
2. A→E→H→G

Всего 6 кратчайших путей.

Ответ: 6