1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Which is larger, $4^{3^{2^1}}$ or $2^{3^{4^1}}$? $\endgroup$ – Matthew Conroy Dec 19 '13 at 4:31
  • 1
    $\begingroup$ I see what you have shown there. I was being way too sloppy. Thanks! $\endgroup$ – PandaMan Dec 19 '13 at 4:38
  • $\begingroup$ The operation is not associative. So you have to say where the brackets go to give meaning. $\endgroup$ – P Vanchinathan Dec 19 '13 at 4:46
  • $\begingroup$ $2^{3^2}= 2^9 \neq (2^3)^2 = 8^2$ $\endgroup$ – P Vanchinathan Dec 19 '13 at 4:47
  • 1
    $\begingroup$ @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! $\endgroup$ – Matthew Conroy Dec 19 '13 at 5:52
4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ You said it was easy. I saw you suffer from there on. $\endgroup$ – chubakueno Dec 29 '13 at 4:09
  • $\begingroup$ 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 ;) $\endgroup$ – punctured dusk Dec 29 '13 at 9:30
  • $\begingroup$ It happens, it is your karma for offending the problem :) $\endgroup$ – chubakueno Dec 30 '13 at 3:47
1
$\begingroup$

My intuition tells me:

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

is the largest.

It should be obvious.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.