Question

В турнире на 6 вершинах нет циклов. Сколько путей длины 3 в нём есть? (Длина пути — это количество рёбер, которое содержит путь.)

Answer 1

Ответ:

15

Пошаговое объяснение:

перебором на изи, Сириус принял

Answer 2

Если в турнире на 6 вершинах нет циклов, это означает, что он представляет собой турнирную ориентированную граф, в котором каждая пара вершин соединена ровно одним ориентированным ребром в одном направлении (то есть нет ребер, идущих в обратном направлении между парами вершин).

Чтобы найти количество путей длины 3 в таком графе, мы можем рассмотреть различные варианты путей.

1. Путь из вершины A в вершину B длины 3 (A -> X -> Y -> B):

   • Выбираем вершину A (6 вариантов).
   • Выбираем вершину X, которая не равна A или B (4 варианта).
   • Выбираем вершину Y, которая не равна A, B или X (3 варианта).
   • Осталась только вершина B.

2. Путь из вершины A в вершину B длины 3 (A -> X -> Y -> B), но сначала идем в обратном направлении и затем снова в нужном направлении:

   • Выбираем вершину A (6 вариантов).
   • Выбираем вершину X, которая не равна A или B (4 варианта).
   • Выбираем вершину Y, которая не равна A, B или X (3 варианта).
   • Осталась только вершина B.

Общее количество путей длины 3 в таком графе будет равно сумме вариантов из первого и второго случая:

6 * 4 * 3 + 6 * 4 * 3 = 216 путей длины 3 в данном турнире на 6 вершинах, где нет циклов.