In general, if there are $m$ cells and we wish to obtain $2^n$, the answer is \[ T(2^n, m) = 2\left[ \binom n0 + \dots + \binom{n}{m-1} \right] - 1. \] Obviously, $T(2^0,m) = T(2^n,1) = 1$. So we will be done by induction if we prove the following recursion. Claim: If $n \ge 1$ and $m \ge 2$, then \[ T(2^n, m) = T(2^{n-1}, m) + T(2^{n-1}, m-1) + 1. \] Proof. This is actually fairly intuitive; we write out the details below for rigor only. Lower bound: we can construct $2^{n-1}$ using $T(2^{n-1},m)$ steps, then construct another $2^{n-1}$ in the remaining $m-1$ cells using $T(2^{n-1},m-1)$ steps, then merge the two. Upper bound: assume that the last move was a merge of two $2^{n-1}$'s (otherwise at most one step occurs). Color one of the $2^{n-1}$'s red, and the other one blue. Then we can color every number that appeared in the process either red and blue, such that we only merge numbers of the same color. (This is done by recursively rewinding the process.) Assume WLOG the first number written was blue; then at most $T(2^{n-1},m)$ moves take places in blue. Moreover, there is always at least one blue number, meaning the red numbers occupy at most $m-1$ cells, and at most $T(2^{n-1},m-1)$ moves take place. This concludes the proof. \qedhere $\blacksquare$

The answer is $2\sum_{i = 0}^8 \binom{n}{i} - 1$. Call the two types of operations insertions and fuses. At any moment, the number of non-empty cells increases by 1 when performing an insertion and decreases by 1 when performing a fuse. Thus the number of insertions is one more than the number of fuses, and it is sufficient to find the maximum possible number of insertions. Notice that the sum of the numbers on the cells increases when performing an insertion, while it stays equal when a fuse is performed. Thus, finding the maximal number of insertions is equivalent to finding the maximal number of sums that may be achieved during the process. We claim that at any point, the sum of the numbers in the cells is a number with at most $8$ binary digits equal to $1$. Indeed, after performing all possible fuses we obtain a state where all of the cells have different numbers on them, implying that the sum has at most $9$ binary digits equal to $1$, because there are only $9$ cells. However, if it had exactly nine, then no further moves would be possible, contradicting the fact that $2^n$ is reached at some point. Thus at any point the sum has at most eight non-zero binary digits. Now we show that it is possible to perform the process in such a way that every sum with at most eight non-zero binary digits is achieved at some point. Let $S$ be the sum at some point, and let $S'$ be the next smallest number with at most non-zero binary digits. It suffices to prove that $S' - S$ is a power of $2$. If $S$ ends in $1$ in binary then $S' = S + 1$. This also holds if $S$ ends in $0$ and has less than $8$ non-zero binary digits. Finally, if $S$ has eight nonzero binary digits, let the rightmost binary $1$ of $S$ be in the $i$-th position from the right. Then clearly $S' = S + 2^{i - 1}$. So $S' - S$ is a power of $2$ always, so because $S$ has at most eight binary ones, we can insert this power of $2$ to obtain a collection with sum $S'$. So it is possible to achieve every one of these sums, of which there are $1 + \sum_{i = 0}^{8} \binom{n}{i}$, which implies that $\sum_{i = 0}^{8} \binom{n}{i}$ insertions are performed, giving the desired answer.

It's much more natural to work backwards in this problem, so we define to moves, the delete (take any element and delete it, leaving an empty space), and the split (turn a $2^k$ into a $2^{k-1}$ and a $2^{k-1}$ in some cell that was blank). If some number was made from splitting some number $x$, then the split numbers are called the children of $x$. Future grandchildren or great-grandchildren are called descendants of $x$. The question is, starting with one $2^n$, what is the maximum number of moves that lead to everything blank? Let $f(m,n)$ be the answer where we have $m$ cells (the answer to the problem is $f(9,n)$). We claim \[f(m,n)=f(m,n-1)+f(m-1,n-1)+1.\]Claim 1: $f(m,n)\le f(m,n-1)+f(m-1,n-1)+1$ Proof of claim 1: In other words, we have to show that if we get from one $2^n$ to all blank, we used at most $f(m,n-1)+f(m-1,n-1)+1$ moves. The first move is clearly a split, so now we have two $2^{n-1}$s. Let $A$ be the $2^{n-1}$ whose descendants are the last to disappear, and let $B$ be the other $2^{n-1}$. Then, whenever $B$'s family splits, there is always some $A$ around, so $B$'s splitting and eventual disappearing is done in at most $m-1$ spaces, so the amount of moves it takes for $B$ to split and die is at most $f(m-1,n-1)$. The amount of moves for $A$ is at most $f(m,n-1)$ trivially. Since there was one split move at the beginning, we have at most $1+f(m-1,n-1)+f(m,n-1)$ moves in total, as desired. Claim 2: $f(m,n)\ge f(m,n-1)+f(m-1,n-1)+1$ Proof of claim 2: This is quite simple once we have proved claim 1. Split the $2^n$ into two children, $A$ and $B$. Then let $B$ fully split and die in the max number of moves, and this takes $f(m-1,n-1)$ moves. Then let $A$ fully split and die, and this takes $f(m,n-1)$ moves, so we split and deleted the original $2^n$ in at most $1+f(m,n-1)+f(m-1,n-1)$ moves, as desired. Therefore, $f(m,n)=f(m,n-1)+f(m-1,n-1)+1$ with base cases $f(m,0)=f(1,n)=1$.

I got this: v_Enhance wrote: If $n \ge 1$ and $m \ge 2$, then \[ T(2^n, m) = T(2^{n-1}, m) + T(2^{n-1}, m-1) + 1. \] v_Enhance wrote: The answer is \[ T(2^n, m) = 2\left[ \binom n0 + \dots + \binom{n}{m-1} \right] - 1. \] But how did you get this? I just bashed it and got the 8th degree polynomial

Can anyone show how from recursive formula to get closed form?

FISHMJ25 wrote: Can anyone show how from recursive formula to get closed form? pandadude wrote: But how did you get this? I just bashed it and got the 8th degree polynomial I solved it using recursive method on the TST by guessing the solution. Basically, I inducted that the answer must be a $8$-th degree polynomial satisfying $P(0) = 1, P(1) = 3, P(2) = 7,...,P(8) = 2^9-1$. Luckily, I know that $Q(x) = \tbinom{x}{0} + \tbinom{x}{1} + ... + \tbinom{x}{8}$ satisfies $Q(n)=2^n$ for all $n=0,1,2,...,8$ (which is a standard problem). Modifying this to recover $P(x)$ gives the answer.

Can someone further explain the bounds in yayups and kayaks solution. I'm having trouble understanding them.

To form $2^n$, Sir Alex must either form two $2^{n-1}$s and combine them, or put $2^n$ into an empty cell. If he chooses the former, note that the formation of these two $2^{n-1}$s is completely disjoint, so assume he always finishes one of them before moving on to the next. Defining $f(n,x)$ to be the maximum number of moves he can make to form only $2^n$ given a row of $x$ cells, (and $-1$ if this is impossible) it is not hard to see that $$f(n,x)=\max(0,f(n-1,x)+f(n-1,x-1))+1$$based on our previous observations. Now, we will induct upwards to find $f(n,9)$. I claim that $f(n,x)=2\sum_{i=0}^{x-1}\binom{n}{i}-1$. The base case of $x=1$ is obvious, as we can always only make 1 move, as well as when $n=0$, since we can only place a single 1. Now, supposing that we have this formula for all pairs with $x<X$ and $x=X,n<N$, we have $$f(N,X)=2\sum_{i=0}^{X-2}\left(\binom{N-1}{i+1}+\binom{N-1}{i}\right)+1=2\sum_{i=0}^{X-1}\binom{N}{i}-1$$as desired. So, our answer is $2\sum_{i=0}^{8}\binom{n}{i}-1$

There are two ways we can finish the game; either write $2^n$ directly in the beginning, or combine two $2^{n-1}$'s, provided there are no other numbers written. Also note that we can never write a number that is more than $2^n$, since if we did, we could never cancel it out or make it less, so it would be impossible to end with only an $2^n$. Furthermore, we cannot ever write an $2^n$ directly, since we would have to do it at the beginning, and then the game would be over. However, this is not optimal for maximizing the number of moves. Therefore, at the end, we must have two $2^{n-1}$'s only, which we must combine together to end with just one $2^n$. Let $f(n,N)$ be the maximum amount of time to end with an $2^n$, from $N$ cells. There are $f(n-1,N)$ moves to get the first $2^{n-1}$, and $f(n-1,N-1)$ moves to get the second $2^{n-1}$, since one cell it occupied by the $2^{n-1}$, and then one move to combine the two. So \[ f(n,N) \ge f(n-1,N) + f(n-1,N-1)+1. \]Since the two $2^{n-1}$'s are completely disjoint, we can think of working backwards to see that this bound must be sharp. At the end, we must have had two $2^{n-1}$'s. We can then do the process and reverse and see that every number either contributed to the first $2^{n-1}$ or the second $2^{n-1}$. Therefore, \[ f(n,N) = f(n-1,N) + f(n-1,N-1)+1. \]The initial conditions are $f(0,N)=1$ and $f(n,1)=1$ for all $n,N$. We claim that \[ f(n,N)=2\sum_{i=0}^{N-1} \binom{n}{i}-1.\]We prove this with induction on $n$. The base cases are satisfied (note that $\binom{0}{0}=1$). We see that \begin{align*} f(n,N) &= 2\sum_{i=0}^{N-1} \binom{n}{i} - 1 \\ &= 2\sum_{i=0}^{N-1} \left(\binom{n-1}{i} + \binom{n-1}{i-1} \right) -1\\ &= (f(n-1,N)+1) + (f(n-1,N-1)+1) - 1 \\ &= f(n-1,N)+f(n-1,N-1)+1, \end{align*}as desired. Now plug in $N=9$ to get the answer.

It's fairly easy to see that the optimal strategy involves combining two $2^{n-1}$s. Else, he can put $2^n$ into an empty cell, but this clearly does not maximize the moves taken. Now let $s_{x, y}$ denote the maximum number of moves that he can make to form $2^{x}$ given $y$ cells. It follows that $$s_{x, y} = s_{x-1, y} + s_{x-1, y-1} + 1.$$To see this, notice that the formation of both $2^{x-1}$s is disjoint. Now, the maximum amount of moves he can make to form the first $2^{x-1}$ is $s_{x-1, y}$. For the second, there are $y - 1$ cells left, and Sir Alex wants to form $2^{x-1}$. He can do this in $s_{x-1, y-1}$ ways. Lastly, he needs to combine the two $2^{n-1}$s which accounts for one last move. Now suppose that $s_{x, y} = 2 \sum_{i = 0}^{y-1} {x \choose i} - 1$ for all pairs $x \le a$ and $x < b$. This will follow by induction, the base case $x = 1$ being obvious. We have $$s_{a, b} = s_{a-1, b} + s_{a-1, b-1} + 1 = 2 \left( \sum_{i = 0}^{b-2} {a - 1 \choose i+1} + {a - 1 \choose i} \right) + 1 = 2 \sum_{i = 0}^{b-1} {a \choose i} - 1$$and we are done. $\blacksquare$

After spending some time on the problem, as many have mentioned, the key recurrence relation is quite intuitive. However, there is still something unsatisfying about "guessing" the general formula and applying induction, one wonders where solvers obtained the motivation for such a formula. In my case, I found it very useful to compute the values of many such $T(2^n, m)$ (borrowing the notation of v_Enhance). In particular, I noticed that \begin{align*} T(2^8, 9) &= 2^9 - 1\\ T(2^8, 8) &= 2^9 - 3\\ T(2^8, 7) &= 2^9 - 19\\ T(2^8, 6) &= 2^9 - 75 \end{align*}Where the differences between consecutive terms are $2, 16, 56 = 2\cdot {8 \choose 0}, 2\cdot {8 \choose 1}, 2\cdot {8 \choose 2}$ This helped me guess the general formula.

The answer is $2\sum_{i=0}^{8}\binom{n}{i}-1$; in general, if one replaces 9 with any $m$, we can substitute $m-1$ in place of $8$. Let the maximum amount of moves one can make to form $2^n$ in $m$ cells be equal to $f(n,m)$ for nonnegative integers $n$ and positive integers $m$. Claim: $f(n,m)=f(n-1,m)+f(n-1,m-1)+1$ for $n\ge 1,m\ge 2$ Proof: Adding $2^n$ obviously is suboptimal, so the final step must have been a merge between two $2^{n-1}$'s. Label them as A and B, and for every $2^j$ inserted into the row, denote it as an A-ancestor if it would eventually be merged into A and define a B-ancestor similarly. WLOG let the first $2^j$ be an A-ancestor; then, throughout the game, there are at most $n$ cells available for the formation of A, and at most $n-1$ (as there must be at least 1 A-ancestor at the board at any point in time) cells available for the formation of B, with the $+1$ accounting for merging A and B. To show that $f(n-1,m)+f(n-1,m-1)+1$ is achievable, we can simply form $2^{n-1}$ in $f(n-1,m)$ steps, and then another $2^{n-1}$ in $f(n-1,m-1)$ steps, and merge these two numbers to finish. One can check that the given formula satisfies the recurrence and its base cases $n=0$ and $m=1$, and hence the proof is complete.

Let \(f(n,k)\) be the maximum number of moves to obtain \(2^n\) using \(k\) cells, so that we desire \(f(n,9)\). I contend that \[f(n,k)=2\sum_{i=0}^{k-1}\binom ni-1.\] Since \(f(n,1)=f(0,k)=1\), it will suffice to show the recurrence \[f(n,k)=f(n-1,k)+f(n-1,k-1)+1.\]Indeed: Claim: \(f(n,k)\ge f(n-1,k)+f(n-1,k-1)+1\) for all \(n\), \(k\). Proof. First we may construct a single cell containing \(2^{n-1}\) with \(k\) cells in \(f(n-1,k)\) moves, then another \(2^{n-1}\) with the remaining \(k-1\) cells in \(f(n-1,k-1)\) moves, and finally we may combine these two to form a single \(2^n\) in one move. \(\blacksquare\) Claim: \(f(n,k)\le f(n-1,k)+f(n-1,k-1)+1\) for all \(n\), \(k\). Proof. Without loss of generality, let the first number ever written be in the leftmost square, and say that whenever the leftmost number combines with another number, the result is written in the leftmost square. Then right before \(2^n\) is obtained, the leftmost square contains a \(2^{n-1}\), constructed in at most \(f(n-1,k)\) moves, and another square contains a \(2^{n-1}\), constructed in at most \(f(n-1,k-1)\) moves (since if the leftmost square were ever involved in creating the rightmost \(2^{n-1}\), the \(2^{n-1}\) be written in the leftmost square). The claim follows. \(\blacksquare\)

Let $f(x, y)$ be the maximum number of moves needed to create $2^x$ with $y$ cells. We see that the only way to make $2^x$ is to make $2^{x-1}$ with $y$ cells, then make $2^{x-1}$ with $y-1$ cells, and finally combine the two with one move. This results in the recurrence \[f(x, y) = f(x-1, y) + f(x-1, y-1) + 1.\] Moreover, we have $f(x, 1) = 1$ for all $x$, since there is only one way to create $2^x$ with one cell. Now, we claim that \[f(x, y) = 2\left(\binom{x}{0} + \binom{x}{1} + \cdots + \binom{x}{y-1}\right) - 1.\] We prove this via induction. Note that $f(0, y) = 1$ for all $y$, so the base case is true. For our inductive step, note that \begin{align*} f(x-1, y) + f(x-1, y-1) + 1 & = 2\left(\binom{x-1}{0} + \binom{x-1}{1} + \cdots + \binom{x-1}{y-1}\right) - 1\\& + 2\left(\binom{x-1}{0} + \binom{x-1}{1} + \cdots + \binom{x}{y-2}\right) - 1\\ & + 1\\ & = 2\left(\binom{x}{0} + \binom{x}{1} + \cdots + \binom{x}{y-1}\right) - 1\\ & = f(x, y). \end{align*} Then our desired answer is $f(n, 16)$, which is \[2\left(\binom{16}{0} + \binom{16}{1} + \cdots + \binom{16}{n-1}\right) - 1.\]

Grizzy wrote: Let $f(x, y)$ be the maximum number of moves needed to create $2^x$ with $y$ cells. We see that the only way to make $2^x$ is to make $2^{x-1}$ with $y$ cells, then make $2^{x-1}$ with $y-1$ cells, and finally combine the two with one move. This results in the recurrence \[f(x, y) = f(x-1, y) + f(x-1, y-1) + 1.\] Moreover, we have $f(x, 1) = 1$ for all $x$, since there is only one way to create $2^x$ with one cell. Now, we claim that \[f(x, y) = 2\left(\binom{x}{0} + \binom{x}{1} + \cdots + \binom{x}{y-1}\right) - 1.\] We prove this via induction. Note that $f(0, y) = 1$ for all $y$, so the base case is true. For our inductive step, note that \begin{align*} f(x-1, y) + f(x-1, y-1) + 1 & = 2\left(\binom{x-1}{0} + \binom{x-1}{1} + \cdots + \binom{x-1}{y-1}\right) - 1\\& + 2\left(\binom{x-1}{0} + \binom{x-1}{1} + \cdots + \binom{x}{y-2}\right) - 1\\ & + 1\\ & = 2\left(\binom{x}{0} + \binom{x}{1} + \cdots + \binom{x}{y-1}\right) - 1\\ & = f(x, y). \end{align*} Then our desired answer is $f(n, 16)$, which is \[2\left(\binom{16}{0} + \binom{16}{1} + \cdots + \binom{16}{n-1}\right) - 1.\] "We see that the only way to make $2^x$ is to make $2^{x-1}$ with $y$ cells, then make $2^{x-1}$ with $y-1$ cells, and finally combine the two with one move. This results in the recurrence" This only proves the lower bound \[f(x, y) \leq f(x-1, y) + f(x-1, y-1) + 1.\], and not the whole recurrence, as you claimed.

Let $f(n,m)$ denote the maximal number of moves to form one cell of $2^n$ given $m$ cells. We claim $$f(n,m) = -1 + 2\sum_{k=0}^{m-1} \binom nk.$$Note that if we use $m$ cells to produce $2^{n-1}$ and the remaining $m-1$ cells to produce another $2^{n-1},$ adjoining them together, we can create $2^n$ in $f(n-1,m) + f(n-1, m-1) + 1$ moves, so $f(n,m) \ge f(n-1,m) + f(n-1, m-1) + 1.$ Moreover, note that any cell must be used to merge into exactly one $2^{n-1},$ so in fact the cells and moves used in $f(n-1, m)$ and $f(n-1,m-1)$ are distinct, so we have $f(n,m)$ must be exactly $f(n-1,m) + f(n-1, m-1) + 1.$ From here, extracting the answer format follows from induction. Remark: Answer extraction is motivated/found by rewriting $g(n,m) = f(n,m) + 1,$ for which the recursion is then $g(n,m) = g(n-1,m) + g(n-1, m-1),$ resembling Pascal's Identity. Arranging $g(n,m)$ values in a pascal-like triangle makes the answer extraction much more obvious.

Idk how to feel about the problem because it's both interesting and unsatisfying We solve the general question: let $f(n,m)$ denote the answer for $2^n$ and $9$ replaced with $m$. Then, the answer is $$f(n,m)=2\left(\binom{n}{0}+\cdots+\binom{n}{m-1}\right)-1.$$Clearly $f((0,m)=f(n,1)=1$ for all $m,n$. Now, the key claim is the following recursion: $$f(n,m)=f(n-1,m)+f(n-1,m-1)+1~\forall n\geq 1, m\geq 2$$To prove that $f(n,m)$ is at least this value (construction), first create $2^{n-1}$ with the $m$ available cells. Then ignore the cell where $2^{n-1}$ is, and then create $2^{n-1}$ with the remaining $m-1$ cells. Finally, merge these to create $2^n$. To prove that $f(n,m)$ is at most this value (bound), note that unless we just start by adding $2^n$ (in which case there is one move), we must finish by merging two copies of $2^{n-1}$. Then the numbers that merge into one of the $2^{n-1}$'s don't interact with those merging into the other one (this is intuitive to see), hence we can WLOG assume that we create one of the $2^{n-1}$'s first without making anything else, then create the next. Then we need at most $f(n-1,m)$ moves for the first $2^{n-1}$ and $f(n-1,m-1)$ moves for the second $2^{n-1}$, and one move to merge. Finally, note that \begin{align*} f(n-1,m)+f(n-1,m-1)&=2\left(\binom{n-1}{0}+\cdots+\binom{n-1}{m-1}+\binom{n-1}{0}+\cdots+\binom{n-1}{m-2}\right)-2\\ &=2\left(\binom{n-1}{1}+\cdots+\binom{n-1}{m-1}+\binom{n-1}{0}+\cdots+\binom{n-1}{m-2}\right)-2\\ &=2\left(\binom{n}{0}+\left(\binom{n-1}{1}+\binom{n-1}{0}\right)+\left(\binom{n-1}{2}+\binom{n-1}{1}\right)+\cdots+\left(\binom{n-1}{m-1}+\binom{n-1}{m-2}\right)\right)-2\\ &=2\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{m-1}\right)-2\\ &=f(n,m)-1 \end{align*}by Pascal's identity, so we're done. $\blacksquare$

We claim the answer is $\displaystyle\sum_{i=0}^{8}2\binom ni-1$. We will solve the general problem where there are $k$ total cells. In every move, the sum of the numbers either stays the same or increases by a power of $2$. Therefore, the sum has at most $k$ ones in binary. However, if all $k$ of the numbers are distinct, then it is impossible to make another move, so there must be at most $k-1$ ones in binary, so there can be at most $\displaystyle\sum_{i=0}^{k-1}\binom ni$ moves of the first type. Then, since the second move decreases the number of numbered cells by one, there can be at most $\displaystyle\sum_{i=0}^{k-1}\binom ni-1$ moves of the second type, which gives a total of $\displaystyle\sum_{i=0}^{k-1}2\binom ni-1$ total moves. Now, we will show that this is achievable by induction on $n$. Base Case: $n=0$ or $k=1$ Then, if $n=0$, writing $1$ in an empty cell works and takes $1$ move. We have $\displaystyle\sum_{i=0}^{k-1}2\binom 0i-1=1$. If $k=1$, then writing $2^n$ works and takes $1$ move. We have $\displaystyle\sum_{i=0}^02\binom ni-1=1$. Inductive Step: First, we can write $2^{n-1}$ using $\displaystyle\sum_{i=0}^{k-1}2\binom{n-1}i-1$ moves. Then, we can write $2^{n-1}$ again by using the $k-1$ remaining cells using $\displaystyle\sum_{i=0}^{k-2}2\binom{n-1}i-1$ by the inductive hypothesis. Finally, we use one more move to turn the two $2^{n-1}$s into a $2^n$. The total number of moves is \begin{align*} \sum_{i=0}^{k-1}2\binom{n-1}i-1+\sum_{i=0}^{k-2}2\binom{n-1}i-1+1&=1+\sum_{i=1}^{k-1}2\binom{n-1}i+\sum_{i=0}^{k-2}2\binom{n-1}i\\ &=1+\sum_{i=0}^{k-2}2\left(\binom{n-1}{i+1}+\binom{n-1}i\right)\\ &=1+\sum_{i=0}^{k-2}2\binom n{i+1}\\ &=\sum_{i=0}^{k-1}2\binom ni-1. \end{align*} Therefore, if $k=9$, then the maximum number of moves is $\boxed{\displaystyle\sum_{i=0}^{8}2\binom ni-1}$.

This is basically the game 2048, so I will call cells with numbers as "tiles", the first action as "spawning a tile", and the second action as "merging tiles". We use recursion. Let $S_{n,k}$ be the maximum number of moves to make the tile $2^n$ with $k$ spaces. Clearly, $S_{n,1}$ for any $n$ is just $1$ because you have to just spawn the tile $2^n$. Also, $S_{1,k}$ for positive integers $k>1$ is just $3$ because you spawn two $1$s then merge them. Now, for $n,k>1$, we can see that $S_{n,k}=S_{n-1,k}+S_{n-1,k-1}+1$ because you first have to make a $2^{n-1}$, then make another $2^{n-1}$ with one less space, then merge them. At this point, it is clear that the base cases and recursion are sufficient for all positive integer values of $n,k$. Since $S_{n,1}$ is constant in $n$, we know that $S_{n,2}$ is at most linear in $n$, $S_{n,3}$ is at most quadratic in $n$, etc. Therefore, $S_{n,9}$ is at most $8$th degree in $n$. We can therefore bash out the first $9$ terms of the polynomial from our recurrence relation, which turns out to be $$3,7,15,31,63,127,255,511,1021$$for $n=1,2,3,4,5,6,7,8,9$. Our answer is therefore $$S_{n,9}=\boxed{2\sum_{i=0}^{8}\binom{n}{i}-1}.$$QED.

We will solve the problem for general $n$ and $k$ where $k$ is the number of cells. Note that each time we use operation $1$, the sum of all values in the cells increases. $~$ Note that the number in each cell must be a power of $2$. If all the numbers in the cells are different, then we are stuck. Therefore, the sum of all numbers has at most $k-1$ ones in its base $2$ representation. Thus, there are a total of \[S=\binom{n}{0}+\binom{n}{1}+\dots + \binom{n}{k-1}\]different possible sums less than $2^n$ itself. Therefore, the total number of possible times that operation $1$ was done is just $S$. Note that the number of operation $2$s is one less than the number of operation $2$s so, Sir Alex made at most $2S-1$ moves. It remains to show that we can achieve every possible sum described. $~$ Now, consider any number which can be represented, $x$. We'll show that the next smallest such number differs by a power of $2$. If there are less than $k-1$ ones in binary, then the next largest is simply adding $1$, which cannot exceed $k-1$ ones. If there are $k-1$ ones in binary and there is a $1$ at the end also add $1$. If there are $k-1$ ones in binary and there is a $0$ at the end, then consider the rightmost $1$. If we change anything to the right of that, we might as well just not change them to get a smaller number that can be represented, so it is also just adding a $1$ if we disregard the zeroes. If we don't disregard the zeroes, it is a power of two. Therefore, the answer is $2S-1$.

Nice problem! I see that many people made a "generalization" but didn't specify the generalized explicit form, nor did they put it in a rigorous way.. I think my solution is pretty cool. We can generalize to making $2^n$ with $k$ squares in the maximum number of moves in the following way: Let $W_{n,k}$ be those number of ways. Notice $W_{1,k}=3\forall k>1,W_{n,1}=1$. It's obvious recursively, we have $$W_{n,k}=W_{n-1,k}+W_{n-1,k-1}+1\stackrel{\text{substitute $W_{n-1,k}$}}{=}W_{n-1,k-1}+W_{n-2,k-1}+W_{n-2,k}+2=\dots$$$$=W_{n-1,k-1}+W_{n-2,k-1}+\dots+W_{1,k-1}+W_{1,k}+n-1;$$in particular, we prove by induction that $W_{n,k}=2\sum_{i=0}^{k-1}\binom ni-1$. Note that W by definition is of the form of a polynomial, which will help with the induction. Base case: $$W_{n,2}=W_{n-1,1}+\dots+W_{1,1}+W_{1,2}+n-1=2n+1=2\sum_{i=0}^{1=k-1}\binom ni-1,$$which holds. Assume henceforth $W_{i-1,k}$ is of this form, and we prove it for $W_{i,k}$. Indeed, $$W_{i,k}=W_{i-1, k} + W_{i-1, k-1} + 1 = 2\left(\binom{i-1}{0} + \binom{i-1}{1} + \cdots + \binom{i-1}{k-1}\right) - 1$$$$+ 2\left(\binom{i-1}{0} + \binom{i-1}{1} + \cdots + \binom{i}{k-2}\right) - 1 + 1= 2\left(\binom{i}{0} + \binom{i}{1} + \cdots + \binom{i}{k-1}\right) - 1.$$The inductive step is complete and plugging in k=16 for the OTIS version, or k=8 for the ISL version gives the answer.

We solve a more general case by defining $f(2^n, k)$ as the maximal number of moves to reach $2^n$ with $k$ cells. We claim our recursion is \[f(2^n, k) = f(2^{n-1}, k) + f(2^{n-1}, k-1) + 1.\] Our construction is derived from building $2^{n-1}$ twice and merging the two. To show that this is an upper bound, we note that we must be merging two $2^{n-1}$ on the final step, or our process is simply spawning $2^n$ in a single step. Using our base cases $f(1,k)=1$ and $f(2^n,1)=1$, we can easily induct to get our explicit form \[f(2^n,k)=\boxed{2\left(\binom{n}{0}+\cdots+\binom{n}{k-1}\right)-1}.\]

Let $s(t)$ be the sum of all numbers in a row in moment $t$ in time. Firstly, note that $s(t)$ can be expressed as a sum of $\leq 9$ powers of two, thus the sum of digits of $s(t)$ in binary is $\leq 9$. Furthermore, if it is equal to $9$, then all $9$ cells are not empty, and different numbers lie in them, thus no next move is possible. Hence the sum of digits of $s(t)$ in binary is always $\leq 8$. Note that the first operation decreases the number of empty cells by $1$, and the second operation increases it by one. In the start we have $9$ empty cells, in the end $8$, so the number of operations $2$ throughout the whole process is one less than the number of operations $1$. Now we will prove that the maximum number of operations $1$ is $\sum_{i=0}^{8} {n \choose i}$, from which the maximum total number of moves will be $2\sum_{i=0}^{8} {n \choose i}-1$ Firstly, note that $0 \leq s(t) \leq 2^n$ for every time moment. There are exactly $\sum_{i=0}^{8} {n \choose i}+1$ numbers between $0$ and $2^n$ that in binary have at most $8$ non-zero digits, from which our bound follows. Secondly, we will show that the following algorithm goes through all such numbers, which would be our example for the desired value: We will always keep our $9$ numbers in a row as a binary represantion of $s(t)$, where numbers decrease(so cell 1 has the biggest value, 9 - the smallest). Then at each step, if our number has $\leq 7$ digits, just add a $1$ in the first empty cell, and then do elimination process(by that I mean if we have two equal numbers, put their sum in the left cell and make the right cell empty, until all non-zero numbers are different). If we have $8$ non-empty cells, put in the last cell the number, that lies in the $8$th cell, and once again do the elimination process I claim this algorithm will go through all numbers with $\leq 8$ digits in binary. If we increased our sum by $1$, we couldn't go past any, and otherwise, if we had $8$ non-empty cells, in $8$th the number was $2^a$, then all numbers from $s(t)+1$ to $s(t)+2^a-1$ have the same $8$ digits and at least one more, but we should have $\leq 8$ digits, so by adding $2^a$ we once again didn't skip any number. So our algorithm works Finally, we proved the answer is $2\sum_{i=0}^{8} {n \choose i}-1$

We will derive a more general formula where there are $k$ cells rather than $16$. Letting $f(n,k)$ be the maximum moves for $2^n$ on $k$ cells, the answer is \[f(n,k) = 2 \sum_{i=0}^{k-1} \binom{n}{i} -1,\] which we will show using a recursive sequence. Notice that \[f(n,k) = f(n-1,k) + f(n-1,k-1)+1,\] for $n \ge 1$ and $k \ge 2$. A rigorous proof of this is shown as follows: Construction: Form $2^{n-1}$ in $k$ cells and then form another $2^{n-1}$ in the remaining $k-1$ cells. Then combining the two of them leads to a valid construction. Upper bound: Note that the $2^n$ must be derived from two copies $2^{n-1}$ since the only other option is for it to be written in directly. Then, we may color the square with the very first number red and WLOG suppose that any number that is combined with the red square will be rewritten in the red square. We will construct $2^{n-1}$ in the red square in at most $f(n-1,k)$; then, the remaining $2^{n-1}$ takes at most $f(n-1, k-1)$ since it cannot involve the red square. Thus, we get $f(n,k) \le f(n-1,k) + f(n-1,k-1)$, as desired.

storage