Find a permutation of this expression to obtain a maximum possible value

Find a permutation $a_1, a_2, ..., a_{1001}$ of the numbers $1,2,...,1001$ such that the expression

$$a_1^{a_2^{a_3^{...^{...^{a_{1001}}}}}}$$

take a maximum possible value.

• Which is larger, $4^{3^{2^1}}$ or $2^{3^{4^1}}$? – Matthew Conroy Dec 19 '13 at 4:31
• I see what you have shown there. I was being way too sloppy. Thanks! – PandaMan Dec 19 '13 at 4:38
• The operation is not associative. So you have to say where the brackets go to give meaning. – P Vanchinathan Dec 19 '13 at 4:46
• $2^{3^2}= 2^9 \neq (2^3)^2 = 8^2$ – P Vanchinathan Dec 19 '13 at 4:47
• @PVanchinathan It is generally implied that one means $2^{(3^2)}$ when one writes $2^{3^2}$, since if one meant $(2^3)^2$ then one should just write $2^{(3\cdot 2)}$. As you say yourself, $2^{3^2}=2^9$. Plus, writing the kind of expression the OP is asking about would just take too many parentheses...Cheers! – Matthew Conroy Dec 19 '13 at 5:52

As your intuition might tell, $$2^{3^{4^{5^{\cdots^{1000^{1001^1}}}}}}$$ will give the largest result.

First of all note that setting $a_i=1$ for $i<1001$ can never give the maximal value. Replacing $1$ to the end of the sequence will give a number larger then the one you had before. So let's just ignore the $1$ from now on.

Now for a proof, we need the following fact:

If $n>1$ is a natural number and $2\leq a<b$, then $b^{a^n}<a^{b^n}$.

Indeed, this inequality is equivalent to $$n\ln(b)-\ln(\ln(b))>n\ln(a)-\ln(\ln(a)).$$

This is true because for every $n>1$, the function $$n\ln(x)-\ln(\ln(x))$$ is strictly increasing over $[2,+\infty[$. (Its derivative is $\frac nx-\frac1{x\ln x}$ which is strictly postive since $\ln(x)\geq\ln(2)>\frac12\geq\frac1n$.)

Using the above fact a few times you can easily show that $2^{3^{\cdots^{1001}}}$ is the maximum:

Let $2=a_i$. Let's show that it's better to set $a_1=2$.

If $1<i<1000$, we have ${a_{i-1}}^{2^n}<2^{{a_{i-1}}^{n}}$ because of the lemma, where $n={a_{i+1}}^{{a_{i+2}}^{\cdots^{a_{1000}}}}$. So we obtain a larger number by switching $2$ with $a_{i-1}$. We can repeat this until we have $a_1=2$.

If $i=1000$ we can't just use the same trick because $n=1$ in this case. Even worse, $2^3<3^2$!

If $m=a_{999}\geq4$ we can apply the inequality $m^2\leq 2^m$. So certainly we won't get a smaller number when switching $a_{1000}$ with $a_{999}$.

If $m=3$ we can just switch $a_{998}$ with $a_{999}$ (which we know to give a larger number) and then continue as we did in the case $m\geq4$.

Now that we have set $a_1=2$, look where $3$ is in the sequence. You can use similar techniques to make your number larger by letting $3$ descend the power tower down to $a_2$. Then it's $4$'s turn to descend the tower, and so on, and so on...

(To fix some issues at the top of the tower you might want to use the inequality $a^b>b^a$ if $2<a<b$, which can be proved similar to the proof we had before.)

• You said it was easy. I saw you suffer from there on. – chubakueno Dec 29 '13 at 4:09
• Indeed ;) I knew this would be the way to solve it, but I didn't realise the way would be that long. The edit history shows how many difficulties I did't expect ;) – punctured dusk Dec 29 '13 at 9:30
• It happens, it is your karma for offending the problem :) – chubakueno Dec 30 '13 at 3:47

My intuition tells me:

$$2^{3^{4^{5^{\dots^{1000^{1001^1}}}}}}$$

is the largest.

It should be obvious.

• the order from $a_1$ to $a_{1001}$ is $2,3,4,5, \dots, 1000,1001,1$ – wonderich Dec 19 '13 at 4:40
• the bracket on doing exponent here starts from the very top to the bottom. – wonderich Dec 19 '13 at 5:20