# Maximize this score function on a directed tree

Let $$\mathbb N_0^\ast$$ be the set of all finite words/sequences over $$\mathbb N_0$$ and $$\varepsilon$$ the empty word. For a word $$a=(a_1,\ldots,a_n)$$ we define $$\operatorname{len}a:=n$$, $$\Sigma a:=\sum_{k=1}^n a_k$$, $$\operatorname{dep}a:=\operatorname{len}a+\Sigma a$$, $$\max a := \max\{a_k:1\leq k\leq n\}$$ and say $$a\rightarrow b$$ if $$b=(a_1,\ldots,a_{n-1},a_n+1)$$ or $$b=(a_1,\ldots,a_n,0)$$. Now $$T:=(\mathbb N_0^\ast,\rightarrow)$$ is the directed infinite binary tree rooted in $$\varepsilon$$ and $$\operatorname{dep} a$$ is the directed distance from $$\varepsilon$$ to $$a$$ in $$T$$. Assigning a score function $$s:\mathbb N_0^\ast\rightarrow\mathbb R$$ we can now ask to maximize $$s(a)$$ with $$\operatorname{dep}a\leq N$$ for some $$N\in\mathbb N_0$$.

For this particular question set $$s(a) := \sum_{k=1}^{\operatorname{len} a}a_k\cdot\left(1+\max a\right)^{\operatorname{len} a - k + 1}$$ (but feel free to post interesting scores in the comment section).

Now what is the the maximal value of $$s(a)$$ with $$\operatorname{dep} a \leq N$$ and how can it be archieved? Non-trivial lower bounds would be appreciated too if the question turns out to be too hard (in a computational sense).

My gut feeling is something like $$(K,0,\ldots,0)$$ (but what would $$K$$ be depending on $$N$$?) or some kind of diagonal solution maybe, but optimization is not my strong suit.

(An interesting variation for another question might be to make this a two-player game (either finite or infinite) and look for winning strategies, when each player can only maximize over the nodes they selected in their turns.)

If this is a known problem, or variation of one, I would appreciate pointers in the comments as well.

If $$a \to b$$ then $$s(b) \ge s(a)$$, so an $$a$$ which maximises $$s(a)$$ subject to $$\operatorname{dep} a \le N$$ has $$\operatorname{dep} a = N$$.
If $$k_1 < k_2$$ and $$a_{k_1} < a_{k_2}$$ then the word obtained by swapping $$a_{k_1}$$ and $$a_{k_2}$$ has a greater score, so the maximising word has symbols in decreasing order.
If we fix $$n$$ and $$\operatorname{dep} a$$ then decrementing $$a_{k_1}$$ to increment $$a_{k_2}$$ ($$k_1 < k_2$$) while maintaining the property of decreasing order cannot increase $$\operatorname{max} a$$; it decreases the multiplier of a higher power of $$1 + \operatorname{max}a$$ to increase the multiplier of a lower power, and in the worse case also decreases $$\operatorname{max}a$$.
Therefore the optimal word is indeed $$K0^i$$ for some $$i$$. We have $$\operatorname{len}a = i+1$$, $$\operatorname{dep}a = K + i + 1 = N$$, and we wish to maximise $$S(K0^i) = K(1+K)^{i+1} = K(1+K)^{N-K}$$. To maximise this numerically for small $$N$$ is straightforward; to do so analytically is trickier.