 Solution

Use the balancing fact proved by the exchange argument in part d: every leaf of an optimal tree has depth $s-1$ or $s$. A full binary tree with this property has all $2^{s-1}$ possible vertices at level $s-1$; at least one of these is split into two deepest leaves. ThusThese inequalities characterize the maximum codeword length exactly:In the suggested notation $m=a{2}^k$, $1\le a<2$, this is $s=k$ for $a=1$ and $s=k+1$ for $1<a<2$. The distinction at a power of two is important.