We use strong induction; when $n = 1$ the claim is obviously true. Suppose it holds for all $n \le N$, and consider a blackboard with $N + 1$ 1's written on it. After $N - 1$ minutes, we're left with two numbers $a_1, a_2$ on the blackboard. Let $S_1$ be the set of 1's (among the $N + 1$ original) which were involved in the computation of $a_1$, and $S_2$ be the set of 1's involved in the computation of $a_2$. Put $s_1 = |S_1|$ and $s_2 = |S_2|$ and note $s_1, s_2 > 0$ and $s_1 + s_2 = N + 1$. By the induction hypothesis, \[a_1 \ge 2^{\frac{4s_1^2 - 4}{3}}\] \[a_2 \ge 2^{\frac{4s_2^2 - 4}{3}}\] so that by the convexity of $f(x) = 2^x$ we have \begin{align*} (a_1 + a_2)^4 &= \left(2^{\frac{4s_1^2 - 4}{3}} + 2^{\frac{4s_2^2 - 4}{3}}\right)^4 \\ &\ge \left(2^{\frac{4s_1^2 + 4s_2^2 - 8}{6} + 1}\right)^4 \\ &\ge \left(2^{\frac{(s_1 + s_2)^2 - 1}{3}}\right)^4 = 2^{\frac{4(N + 1)^2 - 4}{3}} \end{align*} as desired. I wonder if a more direct approach is also possible, by taking base-two logarithms and using the inequality \[4\log_2(x + y) \ge 2\log_2(x) + 2\log_2(y) + 4\] so that instead we have a starting row of $0$s and the transformation $\{x, y\} \rightarrow 2x + 2y + 4$ (somewhat in the spirit of this).

It can be shown that the sum of $\sqrt{\frac{4}{3}+\log_2(x)}$, for all $x$ written on the blackboard, is non decreasing. (Indeed, $\sqrt{\frac{4}{3}+\log_2(x)}+\sqrt{\frac{4}{3}+\log_2(y)}\le \sqrt{2(\frac{8}{3}+\log_2(x)+\log_2(y))} =\sqrt{2(\frac{8}{3}+\log_2(xy)}=\sqrt{\frac{4}{3}+\log_2(4{x^2}{y^2})}\le \sqrt{\frac{4}{3}+\log_2({(x+y)^4})}$.) Then $n\sqrt{\frac{4}{3}}\le \sqrt{\frac{4}{3}+\log_2(M)}$, so $M \ge 2^{\frac{4n^2-4}{3}} $. ($M$ is the number on the board after $n-1$ minutes)

We know that $(x+y)^4 \geq 16(xy)^2$ for all $x,y \in \mathbb{R}^+$. Hence, if $M$ is the last number, then $M$ would have the form: $$M \geq 16(xy)^2 \geq 16(16(x'y')^2y)^2 \geq 16(16(16(x''y'')^2)^2y)^2 \geq 16(16(16(x''y'')^2)^2 16(x'''y''')^2)^2 \geq \cdots \geq 16^S$$ In the end, all the variables vanished since we are initially given $n$ $1$s and so their product reduces to one. Now, we note that the power of any $"16 "$ term is always a power of $2$ because we are squaring it again and again. Further, $S$ (which is the exponent of $16)$ can contain at most one $1$, at most two $2$s, at most four $4$s, etc. In general, the $i$th power of $2$ appears at most $2^i$ times. Hence, $S$ is minimized when we choose the lower powers (of $2)$ as many times as possible rather than the larger powers. Thus, if $n=2^y+k$ with $0 \le k < 2^y$, then $$S \geq \left( \sum_{i=0}^{y-1} 2^i \cdot 2^i \right)+\underbrace{2^{y}+\cdots +2^{y}}_{k \text{times}} = \left( \sum_{i=0}^{y-1} 4^i \right)+k \cdot 2^y=\frac{4^{y}-1+3k \cdot 2^y}{3} \overset{2^y > k}{ \geq } \frac{(2^y+k)^2-1}{3} = \frac{n^2-1}{3}$$ Hence we get $M \geq 2^{4S} \geq 2^{\frac{4n^2-4}{3}}$, as desired. $\blacksquare$

kmh1 wrote: It can be shown that the sum of $\sqrt{\frac{4}{3}+\log_2(x)}$, for all $x$ written on the blackboard, is non decreasing. (Indeed, $\sqrt{\frac{4}{3}+\log_2(x)}+\sqrt{\frac{4}{3}+\log_2(y)}\le \sqrt{2(\frac{8}{3}+\log_2(x)+\log_2(y))} =\sqrt{2(\frac{8}{3}+\log_2(xy)}=\sqrt{\frac{4}{3}+\log_2(4{x^2}{y^2})}\le \sqrt{\frac{4}{3}+\log_2({(x+y)^4})}$.) Then $n\sqrt{\frac{4}{3}}\le \sqrt{\frac{4}{3}+\log_2(M)}$, so $M \ge 2^{\frac{4n^2-4}{3}} $. ($M$ is the number on the board after $n-1$ minutes) Just a quick note to clear up any possible confusion from this solution. It should be $$\sqrt{2(\frac 8 3 +\log_2(xy))}=\sqrt{\frac 4 3+\log_2(16x^2y^2)}.$$

Strong induct on $n$, with base case $n=1$ trivial. Suppose that after $n-2$ minutes, the numbers $x$ and $y$ are written on the blackboard. The final number on the blackboard must be equal to $$(x+y)^4 \geq \left(2^\frac{{4a^2-4}}{3} + 2^\frac{{4b^2-4}}{3} \right)^4 $$for some positive integers $(a,b)$ with $a+b=n$ by the inductive hypothesis. Now by Jensen's inequality, note that $$\left(2^\frac{{4a^2-4}}{3} + 2^\frac{{4b^2-4}}{3} \right)^4 \geq \left(2^{ \frac{{4(a^2+b^2)-2}}{6}} \right)^4 = \left(2^{ \frac{{2(a^2+b^2)-1}}{3}} \right)^4 \geq \left(2^{ \frac{{n^2-1}}{3}} \right)^4 = 2^{\frac{4n^2-4}{3}},$$as desired. Remarks: Similar to IMO Shortlist 2014 C2, at least in appearance.

Here's a proof with tractability, without using induction or invariant. $abc$. We will also find a stronger bound for general $n$ .

). Note $(x+y)^4 \ge 16x^2y^2$. Further taking $\log 2$, we obtain it suffices to show the following: reduced problem (with leap of faith) wrote: $n$ 0's are written and each minute we replace some two $x,y$ with $2x + 2y + 4$. Prove number left after $n-1$ minutes is at least $4T(n)$. Define $x * y = 2x + 2y + 4 = 2(x+y+1)$. Note our final number can be represented as something like $$ \textcolor{cyan}( \textcolor{green}( \textcolor{magenta}( 0 * 0 \textcolor{magenta}) * 0 \textcolor{green}) * \textcolor{red}( \textcolor{blue}( 0 * 0 \textcolor{blue}) * \textcolor{yellow}( 0 * 0 \textcolor{yellow}) \textcolor{red}) \textcolor{cyan})$$Note each pair of parenthesis does the following: It creates a new $+4$. Multiplies everything inside it by $2$. We look at what happens to each individual $4$ produced. For each pair $ p_1,p_2$ of parenthesis, let $f(p_1,p_2)$ be the number of parentheses containing $p_1,p_2$ (excluding $p_1,p_2$ itself). Intuitively, $f(p_1,p_2)$ can also be viewed as layer of $p_1,p_2$. We obtain our last number is $$4 \cdot \sum_{p_1,p_2} 2^{f(p_1,p_2)} = 4 \cdot \sum_{p_1,p_2} 2^{\text{layer of } p_1,p_2}$$ Claim: the $i$-th layer has at most $2^i$ pairs. Proof: Basically, inside each parenthesis in layer $i$, there are at most two parenthesis in layer $i+1$, proving our claim by induction. $\square$ Now if we write $n = 2^k + l$ with $0 \le l < 2^k$, then last number is at least (recall $n-1$ parenthese are there in total) $$4 \left( \sum_{i=0}^{k-1} (2^i \cdot 2^i) + l \cdot 2^k \right) = 4T(n)$$This completes the proof. $\blacksquare$

Define the value of a positive integer $k$ as $$\sqrt{\frac{3}{4}\log_2(k)+1}.$$ We claim that the sum of the values of the numbers on the board is nondecreasing, which would solve the problem as the value of the final number is at least $n$. We want to prove the inequality $$\sqrt{\frac{3}{4}\log_2((x+y)^4)+1}\geq \sqrt{\frac{3}{4}\log_2(x)+1}+\sqrt{\frac{3}{4}\log_2(y)+1}$$$$2\sqrt{3\log_2(x+y)+1}\geq \sqrt{3\log_2(x)+4}+\sqrt{3\log_2(y)+4}.$$ By Jensen's, we have $$2\sqrt{\frac{3\log_2(x)+3\log_2(y)+8}{2}}\geq \sqrt{3\log_2(x)+4}+\sqrt{3\log_2(y)+4},$$so it suffices to prove that $$2\sqrt{3\log_2(x+y)+1}\geq 2\sqrt{\frac{3\log_2(x)+3\log_2(y)+8}{2}}.$$Squaring this becomes $$12\log_2(x+y)+4\geq 6\log_2(x)+6\log_2(y)+16$$$$2\log_2(x+y)\geq \log_2(x)+\log_2(x)+2.$$Exponentiating gives $$(x+y)^2\geq 4xy,$$which is clearly true so we are done. \begin{remark} The definition of the "value" is actually taking the answer and reverse solving for $n$. This was motivated by playing with small examples and noticing things like "a 16 is worth two 1s", and that combining size-mismatched numbers makes it worse (as even combining something with something as small as a 1 fourth powers the number), so I conjectured that the corresponding number of 1s is nondecreasing, which led to this solution. \end{remark}

We use induction on $n$ with obvious base case $n=1$. Define $a_i$ as a number formed with $i$ 1's originally present on the board. Consider the two numbers $a_k$ and $a_{n-k}$ remaining after $n-2$ minutes. Our inductive hypothesis tells us \[a_k + a_{n-k} \ge 2^{\frac 43 \left(k^2-1\right)} + 2^{\frac 43 \left((n-k)^2-1\right)} \ge 2 \cdot 2^{\frac 43 \left(\left(\frac n2\right)^2-1\right)} \ge 2^{\frac 13 \left(n^2-1\right)},\] and thus the final number must be at least the desired. $\blacksquare$

We do upwards induction(basically adding another $1$ hence increasing $n$ to $n+1$) by showing that $(2^{\frac{4n^2-4}{3}} + 1)^4 \geq 2^{\frac{4(n+1)^2 - 4}{3}}$. By AM-GM notice that $2^{\frac{4n^2-4}{3}} + 1 \geq 2^{\frac{2n^2 + 1}{3}}$ so $(2^{\frac{4n^2-4}{3}} + 1)^4 \geq 2^{\frac{8n^2 + 4}{3}}$ We wish to show that $2^{\frac{8n^2 + 4}{3}} \geq 2^{\frac{4(n+1)^2 - 4}{3}}$. So then $8n^2 + 4 \geq 4n^2 + 8n$ is true since we get $n^2 - 2n + 1 \geq 0 \iff (n-1)^2 \geq 0$ which is true. Our base cases of $n = 1, 2$ are true so we are done.

Proceed by strong induction. Let the minimum score David get be $f(n).$ Assume for $n \le k-1.$ Now for $n = k$, after the first $n-1$ we are left with $a,b.$ Observe that $a \ge f(k), b \ge f(n-k)$ for some $k$ that were used to form $a$. Then, \begin{align*} (a + b)^4 &\ge (f(k) + f(n-k))^4 \\ &\ge 16 (2^{\frac{4}{3}(k^2 - 1)})^2 (2^{\frac{4}{3}((n-k)^2 - 1)})^2 \tag{AM-GM} \\ &\ge 2^{\frac{4}{3} ((n - 2k)^2 + n^2 - 1)} \ge 2^{\frac{4}{3} (n^2 - 1)} \end{align*}completing the inductive step.

dolphinday wrote: We do upwards induction(basically adding another $1$ hence increasing $n$ to $n+1$) by showing that $(2^{\frac{4n^2-4}{3}} + 1)^4 \geq 2^{\frac{4(n+1)^2 - 4}{3}}$. By AM-GM notice that $2^{\frac{4n^2-4}{3}} + 1 \geq 2^{\frac{2n^2 + 1}{3}}$ so $(2^{\frac{4n^2-4}{3}} + 1)^4 \geq 2^{\frac{8n^2 + 4}{3}}$ We wish to show that $2^{\frac{8n^2 + 4}{3}} \geq 2^{\frac{4(n+1)^2 - 4}{3}}$. So then $8n^2 + 4 \geq 4n^2 + 8n$ is true since we get $n^2 - 2n + 1 \geq 0 \iff (n-1)^2 \geq 0$ which is true. Our base cases of $n = 1, 2$ are true so we are done. If I am not mistaken, this fails to take into account when David's strategy does not rely on leaving $1$ for the end. He is not playing optimally btw, rather we want to prove no matter his score, it is greater than $2^{\frac{4}{3}(n^2 - 1)}.$

Aaryabhatta1 wrote: dolphinday wrote: We do upwards induction(basically adding another $1$ hence increasing $n$ to $n+1$) by showing that $(2^{\frac{4n^2-4}{3}} + 1)^4 \geq 2^{\frac{4(n+1)^2 - 4}{3}}$. By AM-GM notice that $2^{\frac{4n^2-4}{3}} + 1 \geq 2^{\frac{2n^2 + 1}{3}}$ so $(2^{\frac{4n^2-4}{3}} + 1)^4 \geq 2^{\frac{8n^2 + 4}{3}}$ We wish to show that $2^{\frac{8n^2 + 4}{3}} \geq 2^{\frac{4(n+1)^2 - 4}{3}}$. So then $8n^2 + 4 \geq 4n^2 + 8n$ is true since we get $n^2 - 2n + 1 \geq 0 \iff (n-1)^2 \geq 0$ which is true. Our base cases of $n = 1, 2$ are true so we are done. If I am not mistaken, this fails to take into account when David's strategy does not rely on leaving $1$ for the end. He is not playing optimally btw, rather we want to prove no matter his score, it is greater than $2^{\frac{4}{3}(n^2 - 1)}.$ Oh thanks for pointing that out, I think I see how I can solve it without assuming that $1$ is at the end.

We use strong induction on $n$. The base case $n =1$ is vacuous. For the inductive step, let $f(x)$ be the smallest possible number that could remain on the board given that there were $x$ 1's initially. Moreover, assume that the inductive hypothesis holds for all $n = 1, 2, \dots, k-1$. Suppose that the two numbers left on the board after $k-2$ minutes are $A$ and $B$ such that David uses $a$ 1's to form $A$ and $b$ 1's to form $B$. We have \begin{align*} (A+B)^4 &\ge (f(a)+f(b))^4 \\ & \ge 16 (f(a)f(b))^2 \\ & = 16 ((2^{\frac{4a^2-4}{3}})(2^{\frac{4a^2-4}{3}}))^2 \\ & = 16 (2^{\frac{4}{3}(a^2-b^2-2)})^2 \\ & = 2^{\frac{4}{3}(2a^2-2b^2-1)} \\ & = 2^{\frac{4}{3}((a+b)^2+(a-b)^2-1)} \ge 2^{\frac{4}{3}((a+b)^2-1)}, \end{align*} which completes the induction as $a+b = k$. $\blacksquare$

We prove this by strong induction on $n$. Say we've proved it for all $n \le k$. We prove it for $n = k+1$. (Of course, $n = 1$ is by default.) Consider the situation after $k-1$ moves. Then we have two numbers, formed using $a$ and $b$ 1's respectively, where $a + b = k+1$. Then these values are at least $2^{\frac{4a^2-4}{3}}$ and $2^{\frac{4b^2-4}{3}}$. Our claim is as follows: $$(2^{\frac{4a^2-4}{3}} + 2^{\frac{4b^2-4}{3}})^4 \ge 2^{\frac{4(a+b)^2-4}{3}}.$$This suffices to finish the induction. The proof is as follows. $$(2^{\frac{4a^2-4}{3}} + 2^{\frac{4b^2-4}{3}})^4 \ge (2^{\frac{2a^2+2b^2-1}{3}})^4 \text{ by AM-GM}$$$$\ge (2^{\frac{(a+b)^2-1}{3}})^4 \text{ by RMS-AM}$$ $$ = 2^{\frac{4(a+b)^2-4}{3}}.$$$\square$