Two Looming Towers Of Powers

The answer is 11.

Let A and B be the first and second sequences, respectively. Note that 16 and 27 are in A and B respectively, so the minimum is at most 11.

Now, note that any number from A is even, and any number from B is odd, so the difference has to be an odd number. Any number in A will be indivisible by 3 while any number in B is divisible by 3, so the difference can't be 3 or 9 either. This leaves 1, 5 and 7 as possibilities to be checked.

Case 1: The minimum difference is 1. This implies that, for some $a_i, b_j$ we have (i) $a_i = b_j+1$ or (ii) $a_i = b_j - 1$ . Write $a_i$ as $x^2$ and $b_j$ as $y^3$ . Case 1(i) implies $(x-1)(x+1)=b_j$ . Since $b_j$ is a power of 3, $x-1$ and $x+1$ must also be powers of 3, which is impossible since $x$ is an even power of 2 and $x+1$ will always have remainder 2 mod 3. Case 1(ii) implies $a_i = (y-1)(y^2 + y +1)$ . As $a_i$ is a power of 2, both factors must also be a power of 2. However, $y$ is an odd number, and so $y^+y+1$ is also odd, which cannot be a power of 2. Hence, the minimum difference cannot be 1.

Case 2: The minimum difference is 5. This implies that there exists $a_i = b_j (mod 5)$ in the sequences. However, for $i>2$ , $a_i$ is always $2^{4p}$ and so has remainder 1. (We can trivially ignore the case of $i=2$ where $a_i = 4$ Meanwhile, $b_j$ is always $3 ^ {2q-1}$ and so has remainder 3. Hence the minimum difference can't be 5 either.

Case 3: The minimum difference is 7. Similar to the previous case, this implies that there exists $a_i = b_j (mod 7)$ in the sequences. However, $a_i$ is always $2^c$ , where $c$ is an even power of 2, and hence can be written as $3d+1$ . And so $a_i = 2^{3d+1}$ , which will have a remainder of 2 since $2^3 = 8$ . Meanwhile, $b_j$ is always $3^g$ , where $g$ is a power of 3, and hence can be written as $6h + 3$ . So $b_j = 3^{6h+3}$ . By Fermat's Last Theorem, $3^6$ has remainder 1, and so $b_j = 3^3 = 27 = 6 (mod 7)$ . Thus the minimum difference can't be 7.

As such, we have rejected all possible numbers smaller than 11. Since the case for 11 can be constructed easily, it is the minimum.

I will break my proof into several parts, labelled A to D.

(A) $a_{n+1} < b_{n} < a_{n+2}$ for $n \geq 2$

(B) $b_{n}-a_{n+1} < b_{n+1}-a_{n+2}$ for $n \geq 2$

(C) $a_{n+3}-b_{n+1} > a_{n+2}-b_{n}$ for $n \geq 2$

(D) $b_{n+1}-a_{n+1} > b_{n}-a_{n}$ for $n \geq 2$

---

How parts A, B, C and D lead to the conclusion:

Instead of minimizing $|a_{x}-b_{y}|$ , let's minimize $|b_{y}-a_{x}|$ instead. It is easy to see that $b_{y}>a_{y}$ . We will therefore only focus on $x \geq y$ . For $x<y$ , $b_{y}-a_{x}>b_{y}-a_{y}$ , so the expression is not minimal.

Inequality A tells us that $b_{y}-a_{y+2}<0$ . Therefore, for $x>y+2$ , $|b_{y}-a_{x}|>|b_{y}-a_{y+2}|$ , the expression is not minimal. Therefore, $y \leq x \leq y+2$ .

Inequality B tells us that for $x=y+1$ , to find the minimum value for the expression, we need to only focus on the case where $n$ is the smallest, that is, $n=2$ . It is easy to compute $b_{2}-a_{3}$ , which is $27-16=11$ .

Inequality C can be rewritten as $|b_{n+1}-a_{n+3}|>|b_{n}-a_{n+2}|$ . It tells us that for $x=y+2$ , to find the minimum value of the expression, we need to only focus on the case $a_{4}-b_{2}$ , which is $2^{16}-27$

Inequality D tells us that for $x=y$ , we need to only focus on the least $n$ , that is $n=2$ . Computing $b_{2}-a_{2}$ , we get $3^{3}-2^{2}=23$ .

Out of $11,23$ and $2^{16}-27$ , clearly $11$ is the smallest.

Therefore, if we manage to prove parts A,B,C and D, we will arrive at the conclusion that the minimum value of the expression is indeed $11$ .

Part A: Prove that $a_{n+1} < b_{n} < a_{n+2}$ for $n \geq 2$

To prove that $a_{n+1} < b_{n}$ , we proceed with induction.

Base case $n=2$ :

$16=a_{3} <b_{2}= 27$ is obviously true.

Assuming $a_{n+1} < b_{n}$ is true, we derive

$a_{n+1} \log 2 < a_{n+1} \log 3 < b_{n} \log 3$

$\log 2^{a_{n+1}} <\log 3^{b_{n}}$

$2^{a_{n+1}}<3^{b_{n}}$

$a_{n+2}<b_{n+1}$ as required.

To prove that $b_{n} < a_{n+2}$ , we proceed by induction again.

We will actually prove a stronger condition, that is $4b_{n}<a_{n+2}$

Base case $n=2$ :

$108=4b_{2}< a_{4}= 2^{16}$ is obviously true.

Assuming $4b_{n}<a_{n+2}$ is true,

$4b_{n+1}=4.3^{b_{n}}<4^{b_{n}}.3^{b_{n}}<16^{b_{n}}=2^{4b_{n}}<2^{a_{n+2}}=a_{n+3}$ as required.

Part B: Prove that $b_{n}-a_{n+1} < b_{n+1}-a_{n+2}$ for $n \geq 2$

We proceed by induction.

Base case $n=2$

$27-16=b_{2}-a_{3} < b_{3}-a_{4}= 3^{27}-2^{16}$

Note that

$27-16=11< (3-2)(3^{15}+3^{14}.2+\cdots + 2^{15})= 3^{16}-2^{16}<3^{27}-2^{16}$ , so our base case is true.

Assuming $b_{n}-a_{n+1} < b_{n+1}-a_{n+2}$ is true, rearrange to get

$a_{n+2}-a_{n+1}<b_{n+1}-b_{n}$

$2^{a_{n+2}-a_{n+1}}<2^{b_{n+1}-b_{n}}<3^{b_{n+1}-b_{n}}$

$2^{a_{n+2}-a_{n+1}}-1<3^{b_{n+1}-b_{n}}-1$

$2^{a_{n+1}}(2^{a_{n+2}-a_{n+1}}-1)<3^{b_{n}}(3^{b_{n+1}-b_{n}}-1)$ (This follows from $a_{n+2}<b_{n+1}$ )

$2^{a_{n+2}}-2^{a_{n+1}}<3^{b_{n+1}}-3^{b_{n}}$

$a_{n+3}-a_{n+2}<b_{n+2}-b_{n+1}$

$b_{n+1}-a_{n+2}<b_{n+2}-a_{n+3}$ as required.

Part C: Prove that $a_{n+3}-b_{n+1} > a_{n+2}-b_{n}$ for $n \geq 2$

In other words, we have to prove that $a_{n+3}+b_{n}-b_{n+1}-a_{n+2}>0$ .

But note that

$a_{n+3}+b_{n}-b_{n+1}-a_{n+2}$

$>4b_{n+1}+b_{n}-b_{n+1}-a_{n+2}$

$=3b_{n+1}-a_{n+2}+b_{n}$

$>3a_{n+2}-a_{n+2}+b_{n}$

$=2a_{n+2}+b_{n}$

$>0$ and we are done.

Part D: Prove that $b_{n+1}-a_{n+1} > b_{n}-a_{n}$ for $n \geq 2$

We proceed by induction again.

Base case $n=2$

$3^{27}-16=b_{3}-a_{3} > b_{2}-a_{2}=27-4$ is obviously true.

Rewrite the inequality above as $b_{n+1}-b_{n}>a_{n+1}-a_{n}$ and suppose that this is true.

We have

$3^{b_{n+1}-b_{n}}>3^{a_{n+1}-a_{n}}>2^{a_{n+1}-a_{n}}$

$3^{b_{n+1}-b_{n}}-1>2^{a_{n+1}-a_{n}}-1$

$b_{n+1}(3^{b_{n+1}-b_{n}}-1)>a_{n+1}(2^{a_{n+1}-a_{n}}-1)$ (It is obvious that $b_{n+1}>a_{n+1}$ )

$3^{b_{n}}(3^{b_{n+1}-b_{n}}-1)>2^{a_{n}}(2^{a_{n+1}-a_{n}}-1)$

$3^{b_{n+1}}-3^{b_{n}}>2^{a_{n+1}}-2^{a_{n}}$

$b_{n+2}-b_{n+1}>a_{n+2}-a_{n+1}$ as required.

---

I initially struggled a lot with this proof, mainly because I have no means of proving $b_{n}<a_{n+2}$ . Just as I was going to give up on this proof, Deedlit from MathStackExchange proved a stronger case very cleverly using mathematical induction. Without his/her help, this proof would be impossible to complete , so I guess I will give credit where credit is due.