Maximize this score function on a directed tree

Question

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.

Answer 1

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.