Sum numbers game with numbers $n,n-1,n-2,\ldots,3,2,1,2,3,\ldots,n-2,n-1,n$

Question

On a line, there are $2n-1$ numbers lined up as follows: $$\text{$n$ , $n-1$ , $n-2$ , $\cdots$ , $3$ , $2$ , $1$ , $2$ , $3$ , $\cdots$ , $n-2$ , $n-1$ , $n$}\,.$$ At each step, one can choose any number in the line and add it to each of its neighbours before removing it. The leftmost and rightmost numbers only have one neighbour each. The process stops when there is a single number left. What is its maximum possible value?

This problem is inspired by and a generalization of the one at http://www.micmaths.com/defis/defi_05.html where $n = 5$.

I thought that the optimal would be to start with the number at the centre and then alternate between the left and right neighbour of the previously chosen number. However, it turns out to be not optimal for $n > 3$. But I do not even know the optimal answer for $n = 5$, except that it must be at least $174$.

Answer 1

I'm leaving the intermediate steps here so you can see how the solution developed; to summarize: The result is a hypothesis for a complete solution based on strong numerical evidence but so far without an idea how to prove its optimality. For all $n$, the solution consists of starting at some point up to $3$ slots away from (say, to the right of) the centre (exactly $3$ slots for $n\ge16$), then going outward, always alternating left and right except for sometimes going left twice in a row. The counts of alternating runs before each double left depend subtly on $n$, but they stabilize one after the other, until from $n=216$ on only the last run count changes, with the other $5$ given by $18,17,35,69,139$.

---

Continuing the successful tradition of building on Tad's answers (see Finding real money on a strange weighing device), I noticed that Tad's permutations always arise from interleaving an ascending and a descending sequence. There are only $2^{2n-2}$ such permutations, and since the last two elements in the permutation don't matter, there are only $2^{2n-4}$ such permutations to be tested, so I figured it made sense to systematically try all such permutations. It turns out that Tad's results are optimal among such permutations.

Here are my results; I'm repeating the ones that Tad had already obtained because I'm getting a more "canonical" form of the permutations, which might make it easier to spot patterns.

\begin{array}{ccc} n&\text{bound}&\text{solution}\\\hline 2&6&2, 3, 1\\ 3&21&4, 3, 2, 5, 1\\ 4&63&5, 4, 3, 6, 2, 7, 1\\ 5&174&6, 5, 4, 7, 3, 8, 2, 9, 1\\ 6&466&7, 6, 5, 8, 4, 9, 3, 10, 2, 11, 1\\ 7&1232&8, 7, 6, 9, 5, 10, 4, 11, 3, 12, 2, 13, 1\\ 8&3239&9, 8, 7, 10, 6, 11, 5, 12, 4, 13, 3, 14, 2, 15, 1\\ 9&8501&11, 10, 12, 9, 8, 13, 7, 6, 14, 5, 15, 4, 3, 16, 2, 17, 1\\ 10&22502&12, 11, 13, 10, 14, 9, 8, 15, 7, 6, 16, 5, 17, 4, 3, 18, 2, 19, 1\\ 11&59499&13, 12, 14, 11, 15, 10, 9, 16, 8, 17, 7, 6, 18, 5, 19, 4, 3, 20, 2, 21, 1\\ 12&156678&14, 13, 15, 12, 16, 11, 10, 17, 9, 18, 8, 7, 19, 6, 20, 5, 4, 21, 3, 22, 2, 23, 1\\ 13&411611&15, 14, 16, 13, 17, 12, 18, 11, 10, 19, 9, 20, 8, 7, 21, 6, 22, 5, 4, 23, 3, 24, 2, 25, 1\\ 14&1082450&16, 17, 15, 18, 14, 19, 13, 12, 20, 11, 21, 10, 9, 22, 8, 23, 7, 6, 24, 5, 25, 4, 3, 26, 2, 27, 1\\ 15&2850105&17, 18, 16, 19, 15, 20, 14, 13, 21, 12, 22, 11, 10, 23, 9, 24, 8, 7, 25, 6, 26, 5, 4, 27, 3, 28, 2, 29, 1\\ 16&7522558&19, 18, 20, 17, 21, 16, 15, 22, 14, 23, 13, 12, 24, 11, 25, 10, 9, 26, 8, 27, 7, 6, 28, 5, 29, 4, 3, 30, 2, 31, 1\\ 17&19862032&20, 19, 21, 18, 22, 17, 23, 16, 15, 24, 14, 25, 13, 12, 26, 11, 27, 10, 9, 28, 8, 29, 7, 6, 30, 5, 31, 4, 3, 32, 2, 33, 1 \end{array}

There seems to be a pattern, beginning at $n=11$, of usually alternating steps but adding an extra down step every $5$ steps, but it's not clear exactly how regular that is.

Here's the code.

P.S.: I checked that, beginning at $n=4$, the solution shown is the only one (up to symmetry) that's optimal among these interleaved permutations. Here are the up/down representations, to make it easier to see patterns; the last two arrows are irrelevant, I just included them to make the correspondence with the solutions in numbers above clearer.

\begin{array}{ccc} n&\text{bound}&\text{solution}\\\hline 2&6&\uparrow\downarrow\\ 3&21&\downarrow\downarrow\uparrow\downarrow\\ 4&63&\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 5&174&\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 6&466&\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 7&1232&\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 8&3239&\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 9&8501&\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 10&22502&\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 11&59499&\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 12&156678&\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 13&411611&\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 14&1082450&\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 15&2850105&\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 16&7522558&\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 17&19862032&\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ 18&52296620&\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\\ \end{array}

Next stage: Since the up/down pattern seems to always consist of alternating up/down with some of the downs doubled, I systematically tried all such permutations to check if the pattern that the doubling occurs every $5$ steps persists. It does not; instead, what persists from $n=15$ to $n=35$ is that there are exactly $5$ double downs.

\begin{array}{ccc} \def\u{\uparrow}\def\d{\downarrow} n&\text{bound}&\text{solution}\\\hline 2&6&\u\d\\ 3&21&\u\d\u\d\\ 4&63&\d\d\u\d\u\d\\ 5&174&\d\d\u\d\u\d\u\d\\ 6&466&\d\d\u\d\u\d\u\d\u\d\\ 7&1232&\d\d\u\d\u\d\u\d\u\d\u\d\\ 8&3239&\d\d\u\d\u\d\u\d\u\d\u\d\u\d\\ 9&8501&\d\u\d\d\u\d\d\u\d\u\d\d\u\d\u\d\\ 10&22502&\d\u\d\u\d\d\u\d\d\u\d\u\d\d\u\d\u\d\\ 11&59499&\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\\ 12&156678&\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\\ 13&411611&\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\\ 14&1082450&\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\\ 15&2850105&\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\\ 16&7522558&\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\\ 17&19862032&\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\\ 18&52296620&\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\\ 19&137319583&\d\u\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\\ 20&360144589&\d\u\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\\ 21&944521421&\d\u\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\\ 22&2477100908&\d\u\d\u\d\u\d\u\d\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\\ 23&6496187851&\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\\ 24&17023599948&\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\\ 25&44604984241&\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\\ 26&116811190426&\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\\ 27&305893372041&\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\\ 28&801042337577&\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\\ 29&2097687354880&\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\\ 30&5493183075966&\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\\ 31&14383060457018&\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\\ 32&37658422859324&\d\u\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\\ 33&98594676094434&\d\u\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\\ 34&258133753770289&\d\u\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\\ 35&675827901330148&\d\u\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\\ 36&1769404155218244&\d\u\d\u\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\d\u\d\u\d\u\d\u\d\u\d\\ \end{array}

Here are the same results (with $n=37$ added), encoded as run counts of up/down alternations separated by double downs:

\begin{array}{ccc} n&\text{bound}&\text{solution}\\\hline 2&6&2\\ 3&21&4\\ 4&63&0,4\\ 5&174&0,6\\ 6&466&0,8\\ 7&1232&0,10\\ 8&3239&0,12\\ 9&8501&2,1,3,4\\ 10&22502&4,1,3,4\\ 11&59499&4,3,3,4\\ 12&156678&4,3,3,6\\ 13&411611&6,3,3,6\\ 14&1082450&5,3,3,3,4\\ 15&2850105&5,3,3,3,6\\ 16&7522558&4,3,3,3,3,4\\ 17&19862032&6,3,3,3,3,4\\ 18&52296620&6,3,3,3,3,6\\ 19&137319583&8,3,3,3,3,6\\ 20&360144589&8,3,3,5,3,6\\ 21&944521421&8,3,5,3,5,6\\ 22&2477100908&8,3,5,5,5,6\\ 23&6496187851&8,5,5,5,5,6\\ 24&17023599948&10,5,5,5,5,6\\ 25&44604984241&10,5,5,5,5,8\\ 26&116811190426&12,5,5,5,5,8\\ 27&305893372041&12,5,5,7,5,8\\ 28&801042337577&12,5,5,7,7,8\\ 29&2097687354880&12,5,7,7,7,8\\ 30&5493183075966&12,7,7,7,7,8\\ 31&14383060457018&12,7,7,7,7,10\\ 32&37658422859324&14,7,7,7,7,10\\ 33&98594676094434&14,7,7,9,7,10\\ 34&258133753770289&14,7,7,9,9,10\\ 35&675827901330148&14,7,9,9,9,10\\ 36&1769404155218244&14,9,9,9,9,10\\ 37&4632452165313827&16,9,9,9,9,10\\ \end{array}

Here's a logarithmic plot of the resulting bounds over $n$, with the line corresponding to $\log(y)=0.969098n+0.278972$ fitting the results quite closely:

Since the minimum run count never seems to decrease, I started testing only permutations with a minimum run count, staying below the actual minimum to allow for a bit of backsliding, but gradually increasing the minimum to allow for higher $n$. The number of runs was still free, so a solution with six double downs would have been allowed, but the possibility can't be excluded that such a solution would have had a run count below the minimum and thus would have been disregarded. Here are the results:

\begin{array}{ccc} n&\text{bound}&\text{solution}\\\hline 38&12128128835847001&16,9,9,9,9,12\\ 39&31752024718355852&16,9,9,11,9,12\\ 40&83128328132235590&16,9,9,11,11,12\\ 41&217633961464664291&16,9,11,11,11,12\\ 42&569776076967267411&16,11,11,11,11,12\\ 43&1491697805825447009&18,11,11,11,11,12\\ 44&3905325498008331133&18,11,11,11,11,14\\ 45&10224282933726344858&18,11,11,13,11,14\\ 46&26767541287332858104&18,11,11,13,13,14\\ 47&70078388001734432885&18,11,13,13,13,14\\ 48&183467739835053564767&18,13,13,13,13,14\\ 49&480324957118576986606&18,13,13,13,13,16\\ 50&1257507207702922491305&18,13,13,15,13,16\\ 51&3292196988703000057276&18,13,13,15,15,16\\ 52&8619084603082606409621&18,13,15,15,15,16\\ 53&22565058712862120799568&18,15,15,15,15,16\\ 54&59076093869511275059946&18,15,15,15,15,18\\ 55&154663224262705303376239&18,15,15,15,17,18\\ 56&404913584709450796650491&18,15,15,17,17,18\\ 57&1060077545022388295148722&18,15,17,17,17,18\\ 58&2775319073549490260205088&18,17,17,17,17,18\\ 59&7265879721619865410265014&18,17,17,17,17,20\\ 60&19022320115840525778394696&18,17,17,17,19,20\\ 61&49801080729814231503727780&18,17,17,19,19,20\\ 62&130380922345572385311434722&18,17,19,19,19,20\\ 63&341341686578978588756712358&18,17,19,19,19,22\\ 64&893644137559497376528334504&18,17,19,19,21,22\\ 65&2339590726811740536644613072&18,17,19,21,21,22\\ 66&6125128044738931674365962964&18,17,21,21,21,22\\ 67&16035793409270234188448079012&18,17,21,21,21,24\\ 68&41982252184224178437539670397&18,17,21,21,23,24\\ 69&109910963148283977555790730436&18,17,21,23,23,24\\ 70&287750637273381498350921050654&18,17,23,23,23,24\\ 71&753340948684651092999237722488&18,17,23,23,23,26\\ 72&1972272208788470499474539665204&18,17,23,23,25,26\\ 73&5163475677714219913350689137188&18,17,23,25,25,26\\ 74&13518154824441290411576366555186&18,17,25,25,25,26\\ 75&35390988795697439278822342886782&18,17,25,25,25,28\\ 76&92654811562705166049135736550613&18,17,25,25,27,28\\ 77&242573445892647393746991810953476&18,17,25,27,27,28\\ 78&635065526115828168008464142422480&18,17,27,27,27,28\\ 79&1662623132455441051432954330192870&18,17,27,27,27,30\\ 80&4352803871250866057941284067804134&18,17,27,27,29,30\\ 81&11395788481298729007027429355459050&18,17,27,29,29,30\\ 82&29834561572649264127826347038980028&18,17,29,29,29,30\\ 83&78107896236653244353987095675034922&18,17,29,29,29,32\\ 84&204489127137313012297066889013936544&18,17,29,29,31,32\\ 85&535359485175296566394760822973220276&18,17,29,31,31,32\\ 86&1401589328388601697072447570729328594&18,17,31,31,31,32\\ 87&3669408499990537951967408951471847094&18,17,31,31,31,34\\ \end{array}

It's interesting how first the $18$ and then the $17$ settle down while the remaining numbers continue to increase – that's not what I would have expected from the earlier results.

Update: This interesting behaviour continues. Since from $n=16$ (the first $n$ with five double downs) the next run count tuple could always be obtained by changing some of the run counts by $\pm2$ (in fact, with the sole exception of $n=20\rightarrow n=21$, it could always be obtained by adding $2$ to one of the run counts), I now narrowed the search to such increments. The result is rather surprising (to me). One run count after the other stabilizes, until from $n=216$ on only the last run count changes, that is, the beginning of the solution is fixed, with $5$ double downs in specific places, and after that it's only alternating up/down. I checked that this remains so up to $n=5000$. Thus, despite the sometimes somewhat erratic changes in the run counts at lower $n$, the results yield a plausible hypothesis for a complete solution to the game. To summarize, the assumptions that would have to be validated to prove this hypothesis are that (up to symmetry)

1. beyond $n=12$, the solution continues to result from interleaving an ascending and a descending sequence;
2. beyond $n=18$, the solution continues to consist of alternating ascents and descents, except for some double descents;
3. beyond $n=37$, the minimum of the run counts of alternating runs does not sharply decrease;
4. beyond $n=87$, the number of double descents remains $5$, and the run counts only change by $\pm2$; and
5. beyond $n=216$, only the last run count changes.

The resulting payoffs are very well described by $\log y\simeq0.962445n+0.451906$; the deviation is not visible in a plot for $n$ up to $1000$.

Here are the complete run counts for this hypothesized solution, up to the point at which only the last run count keeps changing:

\begin{array}{cc} n&\text{solution}\\\hline 2&2\\ 3&4\\ 4&0,4\\ 5&0,6\\ 6&0,8\\ 7&0,10\\ 8&0,12\\ 9&2,1,3,4\\ 10&4,1,3,4\\ 11&4,3,3,4\\ 12&4,3,3,6\\ 13&6,3,3,6\\ 14&5,3,3,3,4\\ 15&5,3,3,3,6\\ 16&4,3,3,3,3,4\\ 17&6,3,3,3,3,4\\ 18&6,3,3,3,3,6\\ 19&8,3,3,3,3,6\\ 20&8,3,3,5,3,6\\ 21&8,3,5,3,5,6\\ 22&8,3,5,5,5,6\\ 23&8,5,5,5,5,6\\ 24&10,5,5,5,5,6\\ 25&10,5,5,5,5,8\\ 26&12,5,5,5,5,8\\ 27&12,5,5,7,5,8\\ 28&12,5,5,7,7,8\\ 29&12,5,7,7,7,8\\ 30&12,7,7,7,7,8\\ 31&12,7,7,7,7,10\\ 32&14,7,7,7,7,10\\ 33&14,7,7,9,7,10\\ 34&14,7,7,9,9,10\\ 35&14,7,9,9,9,10\\ 36&14,9,9,9,9,10\\ 37&16,9,9,9,9,10\\ 38&16,9,9,9,9,12\\ 39&16,9,9,11,9,12\\ 40&16,9,9,11,11,12\\ 41&16,9,11,11,11,12\\ 42&16,11,11,11,11,12\\ 43&18,11,11,11,11,12\\ 44&18,11,11,11,11,14\\ 45&18,11,11,13,11,14\\ 46&18,11,11,13,13,14\\ 47&18,11,13,13,13,14\\ 48&18,13,13,13,13,14\\ 49&18,13,13,13,13,16\\ 50&18,13,13,15,13,16\\ 51&18,13,13,15,15,16\\ 52&18,13,15,15,15,16\\ 53&18,15,15,15,15,16\\ 54&18,15,15,15,15,18\\ 55&18,15,15,15,17,18\\ 56&18,15,15,17,17,18\\ 57&18,15,17,17,17,18\\ 58&18,17,17,17,17,18\\ 59&18,17,17,17,17,20\\ 60&18,17,17,17,19,20\\ 61&18,17,17,19,19,20\\ 62&18,17,19,19,19,20\\ 63&18,17,19,19,19,22\\ 64&18,17,19,19,21,22\\ 65&18,17,19,21,21,22\\ 66&18,17,21,21,21,22\\ 67&18,17,21,21,21,24\\ 68&18,17,21,21,23,24\\ 69&18,17,21,23,23,24\\ 70&18,17,23,23,23,24\\ 71&18,17,23,23,23,26\\ 72&18,17,23,23,25,26\\ 73&18,17,23,25,25,26\\ 74&18,17,25,25,25,26\\ 75&18,17,25,25,25,28\\ 76&18,17,25,25,27,28\\ 77&18,17,25,27,27,28\\ 78&18,17,27,27,27,28\\ 79&18,17,27,27,27,30\\ 80&18,17,27,27,29,30\\ 81&18,17,27,29,29,30\\ 82&18,17,29,29,29,30\\ 83&18,17,29,29,29,32\\ 84&18,17,29,29,31,32\\ 85&18,17,29,31,31,32\\ 86&18,17,31,31,31,32\\ 87&18,17,31,31,31,34\\ 88&18,17,31,31,33,34\\ 89&18,17,31,33,33,34\\ 90&18,17,33,33,33,34\\ 91&18,17,33,33,33,36\\ 92&18,17,33,33,35,36\\ 93&18,17,33,35,35,36\\ 94&18,17,33,35,35,38\\ 95&18,17,35,35,35,38\\ 96&18,17,35,35,37,38\\ 97&18,17,35,37,37,38\\ 98&18,17,35,37,37,40\\ 99&18,17,35,37,39,40\\ 100&18,17,35,39,39,40\\ 101&18,17,35,39,39,42\\ 102&18,17,35,39,41,42\\ 103&18,17,35,41,41,42\\ 104&18,17,35,41,41,44\\ 105&18,17,35,41,43,44\\ 106&18,17,35,43,43,44\\ 107&18,17,35,43,43,46\\ 108&18,17,35,43,45,46\\ 109&18,17,35,45,45,46\\ 110&18,17,35,45,45,48\\ 111&18,17,35,45,47,48\\ 112&18,17,35,47,47,48\\ 113&18,17,35,47,47,50\\ 114&18,17,35,47,49,50\\ 115&18,17,35,49,49,50\\ 116&18,17,35,49,49,52\\ 117&18,17,35,49,51,52\\ 118&18,17,35,51,51,52\\ 119&18,17,35,51,51,54\\ 120&18,17,35,51,53,54\\ 121&18,17,35,53,53,54\\ 122&18,17,35,53,53,56\\ 123&18,17,35,53,55,56\\ 124&18,17,35,55,55,56\\ 125&18,17,35,55,55,58\\ 126&18,17,35,55,57,58\\ 127&18,17,35,57,57,58\\ 128&18,17,35,57,57,60\\ 129&18,17,35,57,59,60\\ 130&18,17,35,59,59,60\\ 131&18,17,35,59,59,62\\ 132&18,17,35,59,61,62\\ 133&18,17,35,61,61,62\\ 134&18,17,35,61,61,64\\ 135&18,17,35,61,63,64\\ 136&18,17,35,63,63,64\\ 137&18,17,35,63,63,66\\ 138&18,17,35,63,65,66\\ 139&18,17,35,65,65,66\\ 140&18,17,35,65,65,68\\ 141&18,17,35,65,67,68\\ 142&18,17,35,67,67,68\\ 143&18,17,35,67,67,70\\ 144&18,17,35,67,69,70\\ 145&18,17,35,69,69,70\\ 146&18,17,35,69,69,72\\ 147&18,17,35,69,71,72\\ 148&18,17,35,69,71,74\\ 149&18,17,35,69,73,74\\ 150&18,17,35,69,73,76\\ 151&18,17,35,69,75,76\\ 152&18,17,35,69,75,78\\ 153&18,17,35,69,77,78\\ 154&18,17,35,69,77,80\\ 155&18,17,35,69,79,80\\ 156&18,17,35,69,79,82\\ 157&18,17,35,69,81,82\\ 158&18,17,35,69,81,84\\ 159&18,17,35,69,83,84\\ 160&18,17,35,69,83,86\\ 161&18,17,35,69,85,86\\ 162&18,17,35,69,85,88\\ 163&18,17,35,69,87,88\\ 164&18,17,35,69,87,90\\ 165&18,17,35,69,89,90\\ 166&18,17,35,69,89,92\\ 167&18,17,35,69,91,92\\ 168&18,17,35,69,91,94\\ 169&18,17,35,69,93,94\\ 170&18,17,35,69,93,96\\ 171&18,17,35,69,95,96\\ 172&18,17,35,69,95,98\\ 173&18,17,35,69,97,98\\ 174&18,17,35,69,97,100\\ 175&18,17,35,69,99,100\\ 176&18,17,35,69,99,102\\ 177&18,17,35,69,101,102\\ 178&18,17,35,69,101,104\\ 179&18,17,35,69,103,104\\ 180&18,17,35,69,103,106\\ 181&18,17,35,69,105,106\\ 182&18,17,35,69,105,108\\ 183&18,17,35,69,107,108\\ 184&18,17,35,69,107,110\\ 185&18,17,35,69,109,110\\ 186&18,17,35,69,109,112\\ 187&18,17,35,69,111,112\\ 188&18,17,35,69,111,114\\ 189&18,17,35,69,113,114\\ 190&18,17,35,69,113,116\\ 191&18,17,35,69,115,116\\ 192&18,17,35,69,115,118\\ 193&18,17,35,69,117,118\\ 194&18,17,35,69,117,120\\ 195&18,17,35,69,119,120\\ 196&18,17,35,69,119,122\\ 197&18,17,35,69,121,122\\ 198&18,17,35,69,121,124\\ 199&18,17,35,69,123,124\\ 200&18,17,35,69,123,126\\ 201&18,17,35,69,125,126\\ 202&18,17,35,69,125,128\\ 203&18,17,35,69,127,128\\ 204&18,17,35,69,127,130\\ 205&18,17,35,69,129,130\\ 206&18,17,35,69,129,132\\ 207&18,17,35,69,131,132\\ 208&18,17,35,69,131,134\\ 209&18,17,35,69,133,134\\ 210&18,17,35,69,133,136\\ 211&18,17,35,69,135,136\\ 212&18,17,35,69,135,138\\ 213&18,17,35,69,137,138\\ 214&18,17,35,69,137,140\\ 215&18,17,35,69,137,142\\ 216&18,17,35,69,139,142\\ \end{array}

P.P.S.:

We can get the exact growth rate of the payoff from a recurrence relation. Beyond $n=216$, the beginning of the game is always the same, and the end consists in a pure run of alternating moves. Assume that the last two numbers left standing in the game for $n$ are $a_n$ and $b_n$. Then the game for $n+1$ reaches a point where the four numbers

$$n+1\quad a_n\quad b_n\quad n+1$$

are left, and we combine them into

$$a_n+n+1\quad a_n+b_n\quad n+1$$

and then into

$$2a_n+b_n+n+1\quad a_n+b_n+n+1\;.$$

So

$$ \pmatrix{a_{n+1}\\b_{n+1}}=\pmatrix{2&1\\1&1}\pmatrix{a_n\\b_n}+\pmatrix{n+1\\n+1}\;. $$

The larger of the eigenvalues of the matrix is $(3+\sqrt5)\,/\,2$, with logarithm $0.962424$ in good agreement with the fitted solution.

And one more thing: This perspective also explains why there are only ever a few double descents. If we always alternate, the weight of every number in the payoff is a Fibonacci number; the weight of the first number is $F_{2n-1}$. (The growth rate $(3+\sqrt5)\,/\,2$ is the square of the Fibonacci growth rate, the golden section $(1+\sqrt5)\,/\,2$.) Every double descent costs a bit of this exponential growth. (A more detailed analysis might quantify how much.) So it doesn't pay to incur another double descent just to shift the first number from, say, $4$ to $5$, but it does pay to shift it slightly away from $1$, since significant factors can be gained by that. An attempt at proving the optimality of the solution should probably go in this direction.

Update:

I brought the numerical results quite a bit closer to a rigorous proof. I'm now making only the assumptions that nothing interesting happens at very high $n$ and that the solution interleaves an ascending and a descending sequence, that is, it starts somewhere and then eats its way to the margins to the right and left, but with no assumptions about when it goes left or right. Thus, in terms of my numbered list of assumptions above, I'm only making assumptions $1$ and $5$ and dropped the complicated assumptions $2$ through $4$.

On that basis, the solutions up to $n$ in the thousands can quickly be determined using dynamic programming, as in this code. A record is kept for each interval $[m,n]$ of the "best" ways of reducing that interval to the border points $m$ and $n$, i.e. the "best" sequences of moves in the interior of the interval without playing either $m$ or $n$. The reason for the scare quotes around "best" is that the result is characterized by the two values that $m$ and $n$ end up with, and such pairs of values aren't necessarily comparable. The code keeps track of all pairs that aren't dominated by another pair. The iteration is initialized with intervals $[m,m+1]$ without interior, whose value pairs are simply the pair of initial values at $m$ and $m+1$, and then updated by growing each interval either to the left or the right, collecting results and discarding the dominated ones.

When all intervals in the game for some $n_{\text{max}}$ have been treated, the solutions for all $n\le n_{\text{max}}$ can be read off. I ran this up to $n_{\text{max}}=870$, and the results coincided with the previous ones, showing that the assumptions $2$ to $4$ were justified.

A proof of assumption $1$ might proceed by considering a complete move sequence as a set of alternating sequences like the ones considered here, which meet at their borders from time to time. One would then have to show that the result achieved by two sequences meeting is dominated by the result that could have been achieved by playing the joint interval in a single alternating sequence. This is complicated by the fact that at the time the sequences meet, they don't immediately merge into two points, so results characterized by three or four values may have to be considered. Assumption $5$ might be amenable to some form of asymptotic analysis.

Answer 2

Here are some lower bounds; I computed these by simulated annealing. The notation is best understood by thinking about the problem as follows: at each step, you pick a nonzero number in the line, add it to its nearest nonzero neighbors, and zero it out. So, for $n=3$, a game might run $$ (3,2,1,2,3) \to (3,3,0,3,3)\to (6,0,0,6,3)\to (12,0,0,0,9)\to(21,0,0,0,0).$$ You can encode this game as the permutation $\pi=\{3,2,4,5,1\}$, where we zero out position $i$ at step $i$ for $i<2n-1$; $\pi(2n-1)$ is the location of the final number.

With this notation, here are the best scores I was able to achieve for small values of $n$.

$$\begin{array}{ccc} n & \textrm{bound} & \textrm{solution}\\ \hline 2 & 6 & \{2,3,1\} \\ 3 & 21 & \{2,3,4,5,1\} \\ 4 & 63 & \{5, 4, 3, 6, 2, 7, 1\} \\ 5 & 174 & \{ 6,5,4,7,3,8,2,1,9\} \\ 6 & 466 & \{7, 6, 5, 8, 4, 9, 3, 10, 2, 1, 11\} \\ 7 & 1232 &\{ 6, 7, 8, 5, 9, 4, 10, 3, 11, 2, 12, 13, 1 \} \\ 8 & 3239 & \{9, 8, 7, 10, 6, 11, 5, 12, 4, 13, 3, 14, 2, 1, 15\} \\ 9 & 8501 & \{7, 8, 6, 9, 10, 5, 11, 12, 4, 13, 3, 14, 15, 2, 16, 1, 17\} \\ 10 & 22502 & \{12, 11, 13, 10, 14, 9, 8, 15, 7, 6, 16, 5, 17, 4, 3, 18, 2, 1, 19\} \\ 11 & 59499 & \{9, 10, 8, 11, 7, 12, 13, 6, 14, 5, 15, 16, 4, 17, 3, 18, 19, 2, 20, 1, 21\} \\ 12 & 156678 & \{10, 11, 9, 12, 8, 13, 14, 7, 15, 6, 16, 17, 5, 18, 4, 19, 20, 3, 21, 2, 22, 1, 23\}\\ \end{array} $$