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.


1 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.


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.