Секретные материалы

[Профессор Снэйп]

Злые инопланетные спецслужбы заперли Малдера и Скалли в $n$-мерном гиперкубе, поместив их в комнату с координатами $(0, 0, \ldots, 0)$. Проанализировав ситуацию, агенты пришли к выводу, что в одной из вершин гиперкуба находится выход в родное трёхмерное пространство и что надо обходить все вершины в его поисках.

Скалли, не мудрствую лукаво, выбрала довольно простой способ обхода. Каждой вершине $e$ с координатами $(\varepsilon_1, \ldots, \varepsilon_n)$ она сопоставила число $\alpha(e) = \varepsilon_1 + \varepsilon_2 \cdot 2 + \varepsilon_3 \cdot 4 + \ldots + \varepsilon_n 2^{n-1}$, после чего пустилась в путь по маршруту $\alpha^{-1}(0) \to \alpha^{-1}(1) \to \alpha^{-1}(2) \to \alpha^{-1}(3) \to \ldots \to \alpha^{-1}(2^n-1)$. Малдер решил выпенриться. Он отождествил естественным образом вершины гиперкуба с элементами абелевой группы $\mathbb{Z}_2^n$, потом ввёл на ней умножение и единицу, представив эту группу как поле разложения многочлена $x^{2^n-1}+1$ над простым полем характеристики $2$, выбрал образующую $a$ мультипликативной группы этого поля и пошёл по маршруту $0 \to 1 \to a \to a^2 \to a^3 \to \ldots \to a^{2^n-1}$.

1) Чей маршрут короче, если мерить расстояние обычной евклидовой метрикой в $\mathbb{R}^n$?

2) Сколько общих отрезков пути может оказаться на этих двух маршрутах?

[Утундрий]

(Оффтоп)

Я бы позвонил Бездонной Глотке.
Кстати, а что по этому поводу говорит Кальте Скиннер?

[Профессор Снэйп]

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

Кстати, если считать расстояние между вершинами не по Евклиду, а по отношению соседства (что не так уж и далеко), то это классическая программерская задача: перечислить подмножества $n$-элементного множества так, чтобы каждое следующее было как можно ближе от предыдущего. Даже алгоритм какой-то специальный есть

[venco]

Профессор Снэйп в сообщении #355629 писал(а):

Даже алгоритм какой-то специальный есть

Ага, серый код.

[ИСН]

да-да, он самый