12
$\begingroup$

$2n-1$ numbers are lined up as follows:

$n$ , $n-1$ , $n-2$ , $\cdots$ , $2$ , $1$ , $2$ , $3$ , $\cdots$ , $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$.

$\endgroup$
  • $\begingroup$ How did you get $174$? The maximum I was able to get was $171$. $\endgroup$ – Purak Jun 29 '15 at 12:48
  • 1
    $\begingroup$ @PuRaK: grin Try again! I assure you it is possible. 173 is also possible. $\endgroup$ – user21820 Jun 29 '15 at 12:48
  • $\begingroup$ Ha, finally got it. So f(1)=1 , f(2)=6 , f(3)=21 , f(4)=63 , f(5)=174 as of now? $\endgroup$ – Purak Jun 29 '15 at 13:46
  • $\begingroup$ @PuRaK: Congratulations! Now can you prove that it is optimal? =D $\endgroup$ – user21820 Jun 29 '15 at 13:58
  • 1
    $\begingroup$ $174$ is in fact optimal for $n=5$. There are essentially $9!$ possible plays of the game, but you can save a factor of two by exploiting both the left-right symmetry of the initial setup, and another factor of two since the order of the last two moves doesn't matter. This leaves $9!/4=90720$ possibilities to try, small enough to check directly. Up to the symmetries, there's only one way to achieve $174$. $\endgroup$ – Tad Jul 11 '15 at 16:58
13
+50
$\begingroup$

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:

logarithmic plot of calculated bounds over n

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.

$\endgroup$
  • 1
    $\begingroup$ @user21820: My last update (at the end of the answer) cleans things up a bit; it does away with the more complicated assumptions and allows the solutions for $n$ up to thousands to be calculated quite efficiently on the basis of one simple assumption. $\endgroup$ – joriki Jul 12 '15 at 17:22
  • 1
    $\begingroup$ @martin: No -- that might have been the case before my last update, because I'd restricted it to five double descents, but the new code in the last update doesn't have that restriction, so we know for a fact that there are only five double descents all the way up to $n=870$ (and I could easily check further). And if the number of double descents doesn't change, one of those six run counts has to increase, so the last one can't hit a ceiling. Also note my remark starting "And one more thing", where I try to explain why it makes sense that nothing changes after this. $\endgroup$ – joriki Jul 12 '15 at 20:31
  • 1
    $\begingroup$ @martin: That's what I meant, yes; sorry if that wasn't clear. The penultimate count hits its cealing at $n=216$, and after that the last count increases by $2$. I guess I should have made the table a few lines longer to show that. $\endgroup$ – joriki Jul 12 '15 at 21:18
  • 1
    $\begingroup$ @martin: This is the compiled code for the dynamic progamming version: dropbox.com/s/32ae7exeocopluw/sums.zip?dl=0. You still need a Java runtime to run it, though :-) It should run for a couple of seconds and then output the values of the games up to $n=1000$. $\endgroup$ – joriki Jul 12 '15 at 21:32
  • 1
    $\begingroup$ @joriki brilliant! thank you :) I will have a go at setting up Java runtime - possibly opening a can of worms here ;) $\endgroup$ – martin Jul 12 '15 at 21:35
5
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ @Martin do you mean I've computed the scores incorrectly? Or you've found better solutions? $\endgroup$ – Tad Jul 11 '15 at 22:38
  • $\begingroup$ @martin I included the patterns so they can be verified. They should be correct, but very possibly suboptimal. $\endgroup$ – Tad Jul 11 '15 at 23:04
  • $\begingroup$ able to reproduce your results now - not sure if optimal either, but can't beat them! +1 :) $\endgroup$ – martin Jul 12 '15 at 0:56
  • $\begingroup$ Thanks for your experiments! Though I'm looking for proven optimal solutions, yours already disproves the class of solutions that I thought would include the optimal one. $\endgroup$ – user21820 Jul 12 '15 at 5:42
  • $\begingroup$ @Tad: Nice starter! (+1) I think we can better see what's going on, if the indexes are shifted from $[1, 2n-1]$ to $[-n,n]$. This way we obtain for $n=5, \{1,0,-1,2,-2,3,-3,4,-4\}$. $\endgroup$ – Markus Scheuer Jul 12 '15 at 9:07

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.