= Solution
Suppose a <tree parent> at depth $n-1$, with $n<L$, has an unused outgoing digit. The missing <tree child> gives an empty <code tree> branch at depth $n$. Move any deepest <tree leaf> into that position, retaining all other <codewords> and deleting the abandoned empty branch. The new word has no old word as a prefix, because it lies in an unused branch, and it is not a prefix of any retained word. Its length decreases from $L$ to $n$. With a <full-support finite distribution> this reduces <expected codeword length> by $p_i(L-n)>0$, contradicting optimality. Hence all three <tree children> exist, and each has a descendant <codeword>. In fact \b[every internal <vertex> above depth $L-1$ has all three <tree children>]. Applying this to the <tree parent> of the specified prefix gives the claimed three extensions.
The positive-probability qualification attached only to the specified prefix does not by itself suffice. In the zero-weight example $(p,c)=((1,0,0),(0,10,110))$, choose the positive-probability word $0$, so $n=1<L=3$. There is no word starting with $2$. The deepest <tree leaf> available for relocation has <probability> zero, so the strict-improvement argument fails. This is why the <full-support finite distribution> assumption is used for the structural conclusions.
Back to article page
