Башня степеней

[worm2]

Sicker в сообщении #1378311 писал(а):

Что значит "лексиографически"?

Идём по двум перестановкам от концов к началам, пока текущие элементы совпадают. Когда перестали совпадать — "больше" та, у которой текущий элемент больше.
Например, (4,1,5,2,3) > (1,5,4,2,3), потому что элементы на 5-й позиции совпадают (3), элементы на 4-й позиции совпадают (2), элемент на 3-й позиции больше у 1-й перестановки (5 > 4).

[Sicker]

worm2 в сообщении #1378313 писал(а):

Идём по двум перестановкам от концов к началам, пока текущие элементы совпадают. Когда перестали совпадать — "больше" та, у которой текущий элемент больше.
Например, (4,1,5,2,3) > (1,5,4,2,3), потому что элементы на 5-й позиции совпадают (3), элементы на 4-й позиции совпадают (2), элемент на 3-й позиции больше у 1-й перестановки (5 > 4).

Я не совсем согласен с этим, неужели $1000000000000000000000000^{{{1000}^{10}}^{100}}$ больше чем $100^{{{1000000000000000}^{100}}^{10}}$?

-- 25.02.2019, 13:39 --

Хотя да... а если это такие числа которые я указал в начальных постах?

-- 25.02.2019, 13:40 --

slavav
Отлично, а теперь полное доказательство

[worm2]

Я ошибся в своём лексикографическом порядке. Кажется, дело сложнее.

Прологарифмируем (натуральным логарифмом) башню $n$ раз (т.к. все числа $> e$, то результат определён и положителен).
Нам будут встречаться выражения вида $A^B \ln C + \ln\ln D$, которые нам нужно будет логарифмировать дальше. До тех пор, пока самое большое число $M$ будет сидеть где-то внутри $A^B$, это $A^B$ будет доминировать, поэтому $\ln(A^B \ln C + \ln\ln D)\approx \ln(A^B\ln C)=B\ln A + \ln\ln C$, т.е. с нужной точностью получили выражение того же вида.
Рано или поздно мы набредём на выражение вида $M^B \ln C + \ln\ln D$ (где $M=a_n$ — самое большое число). Приближённое логарифмирование даст $B \ln M + \ln\ln C$, следующее приближённое логарифмирование — $\ln B + \ln\ln M$, и вот в этом выражении уже будет доминировать $\ln\ln M$ (это я так интерпретирую "<<"), поэтому тут уже можно отбросить $\ln B$. Конечный результат будет с нужной точностью равен $\ln \ln ... \ln M$, где логарифмов тем больше, чем раньше нам встретится $M$. Т.е. если максимальное число $M$ в перестановке $x$ встретилось раньше, чем в перестановке $y$, то $(y)>(x)$. А вот если $M$ встретится на одинаковых местах — тогда в дело вступают величины меньшего порядка, а именно $B$, т.е. башня над $M$.

Получается, алгоритм такой:
1) Находим в обеих перестановках место максимального элемента $M(=a_n)$. Если в какой-то перестановке он стоит на месте с большим номером, то эта перестановка "больше".
2) Если $M$ стоит на одинаковых позициях, и эта позиция — последняя, то просто отбрасываем последние элементы и переходим к сравнению меньших башен.
3) Если $M$ стоит на одинаковых позициях, и эта позиция — не последняя, то отсекаем элементы, стоящие левее и переходим к сравнению "остатков башен" над $M$. В этом случае, вообще говоря, башни состоят уже из разных элементов. Нужно сначала выяснить максимальный элемент в первом и во втором "остатках башен", и если он больше у одной из перестановок — то эта перестановка "больше". Если же он присутствует у обоих "остатков" — сравниваем их по п. 1) и т.д.

(1,2)>(2,1)

Сначала приделываем тройку к концу:
(1,2,3)>(2,1,3)
Затем к середине:
(1,3,2)>(2,3,1)
Затем к началу:
(3,1,2)>(3,2,1)
Получаем:
(1,2,3)>(2,1,3)>(1,3,2)>(2,3,1)>(3,1,2)>(3,2,1)

Затем так же последовательно приделываем четвёрку на 4-е, 3-е, 2-е и первое места:
 (1,2,3,4)>(2,1,3,4)>(1,3,2,4)>(2,3,1,4)>(3,1,2,4)>(3,2,1,4)>
>(1,2,4,3)>(2,1,4,3)>(1,3,4,2)>(2,3,4,1)>(3,1,4,2)>(3,2,4,1)>
>(1,4,2,3)>(2,4,1,3)>(1,4,3,2)>(2,4,3,1)>(3,4,1,2)>(3,4,2,1)>
>(4,1,2,3)>(4,2,1,3)>(4,1,3,2)>(4,2,3,1)>(4,3,1,2)>(4,3,2,1)

и т.д.

[ИСН]

Так последние элементы не отбрасываются же. Скажем, $5^4>3^5$, но $5^{4^{10}}<3^{5^{10}}$.

[worm2]

Тут такая извращённая логика (как я её понял), что мы считаем, что $5^4<3^5$, хотя это на самом деле не так.
Потому что тут наибольшее число (здесь это 5) должно быть "много больше" любого другого. Настолько "много больше", насколько мы захотим. А мы хотим, чтобы "A>>B" позволяло нам невозбранно считать, что $X^A>Y^B$ для любых $X$, $Y$ (которые тоже "<< A", однако большие $e$).
Эта логика работает, только если $a_k$ растёт очень, очень быстро (как нам и завещал ТС).

[ИСН]

А, ну тогда может быть.

[Sicker]

worm2

worm2 в сообщении #1378345 писал(а):

3) Если $M$ стоит на одинаковых позициях, и эта позиция — не последняя, то отсекаем элементы, стоящие левее и переходим к сравнению "остатков башен" над $M$. В этом случае, вообще говоря, башни состоят уже из разных элементов. Нужно сначала выяснить максимальный элемент в первом и во втором "остатках башен", и если он больше у одной из перестановок — то эта перестановка "больше". Если же он присутствует у обоих "остатков" — сравниваем их по п. 1) и т.д.

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

worm2 в сообщении #1378345 писал(а):

(1,2)>(2,1)

Сначала приделываем тройку к концу:
(1,2,3)>(2,1,3)
Затем к середине:
(1,3,2)>(2,3,1)
Затем к началу:
(3,1,2)>(3,2,1)
Получаем:
(1,2,3)>(2,1,3)>(1,3,2)>(2,3,1)>(3,1,2)>(3,2,1)

Затем так же последовательно приделываем четвёрку на 4-е, 3-е, 2-е и первое места:
(1,2,3,4)>(2,1,3,4)>(1,3,2,4)>(2,3,1,4)>(3,1,2,4)>(3,2,1,4)>
>(1,2,4,3)>(2,1,4,3)>(1,3,4,2)>(2,3,4,1)>(3,1,4,2)>(3,2,4,1)>
>(1,4,2,3)>(2,4,1,3)>(1,4,3,2)>(2,4,3,1)>(3,4,1,2)>(3,4,2,1)>
>(4,1,2,3)>(4,2,1,3)>(4,1,3,2)>(4,2,3,1)>(4,3,1,2)>(4,3,2,1)

и т.д.

Верно, собственно алгоритм формулируется так:
Сначала смотрим на каком месте находится максимальный элемент $M$ у обоих групп, если у одной из них он находится правее относительно другой, то эта перестановка больше, если левее, то меньше. Если они на равных позициях, то смотрим предыдущий максимальному элемент $M_1$, если он правее у одной перестановки, то она больше и т.д. Если и тут равенство, то переходим к следующему по убыванию элементу и т.д. Это собственно то что вы изобразили

[g______d]

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

[worm2]

Sicker в сообщении #1378415 писал(а):

worm2 в сообщении #1378345 писал(а):

3) Если $M$ стоит на одинаковых позициях, и эта позиция — не последняя, то отсекаем элементы, стоящие левее и переходим к сравнению "остатков башен" над $M$. В этом случае, вообще говоря, башни состоят уже из разных элементов. Нужно сначала выяснить максимальный элемент в первом и во втором "остатках башен", и если он больше у одной из перестановок — то эта перестановка "больше". Если же он присутствует у обоих "остатков" — сравниваем их по п. 1) и т.д.

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

Этот третий пункт — самый интересный. Я сам до конца не уверен в нём.

Цитата:

Если они на равных позициях, то смотрим предыдущий максимальному элемент $M_1$, если он правее у одной перестановки, то она больше и т.д. Если и тут равенство, то переходим к следующему по убыванию элементу и т.д. Это собственно то что вы изобразили

Да, я именно это и изобразил:

Я в сообщении #1378345 писал(а):

(2,3,4,1)>(3,1,4,2)

Но я тут ошибся в своём алгоритме, по нему должно быть другое. По третьему пункту должно быть (2,3,4,1)<(3,1,4,2)! Мы отсекаем всё, что левее четвёрки, и сравниваем $a_1$ и $a_2$. $a_1 < a_2$, значит, (2,3,4,1)<(3,1,4,2). Это минимальный пример, на котором наблюдаются расхождения, давайте его рассмотрим подробнее:

$$a_2^{a_3^{a_4^{a_1}}} \,\,?\,\, a_3^{a_1^{a_4^{a_2}}}$$

Прологарифмируем 2 раза:

$$a_4^{a_1}\ln a_3 + \ln\ln a_2\, \,\,?\,\, \, a_4^{a_2}\ln a_1 + \ln\ln a_3$$

Двойные логарифмы отбрасываем, они меньшего порядка:

$$a_4^{a_1}\ln a_3 \,\,?\,\, a_4^{a_2}\ln a_1$$

Для максимальной ясности ещё раз логарифмируем:

$$a_1\ln{a_4} + \ln\ln a_3 \,\,?\,\, a_2\ln{a_4} + \ln\ln a_1$$

$$(a_1-a_2)\ln{a_4} + \ln\ln\frac{a_3}{a_1} \,\,?\,\, 0$$

Доминирующий член тут $\ln{a_4}>>\ln\ln (a_3/a_1)$. Поэтому знак выражения в левой части определяется знаком $a_1-a_2<0$.