I have solved the first two subsections of an assignment, but I can't solve the last subsection.
We have a Huffman code with probabilities $p_1,p_2,\ldots, p_n$ and we know that $p_1>p_2>\cdots>p_n>0$.
$y_1$ - the code for the character whose probability is $p_1$? And $|y1|$ is the length of $y_1$.
I proved that:
- if $|y_1| = 1$ then $p_1 \geq 1/3$.
- if $p_1 < 1/3$ then $|y_1| \geq 2$ (it is not the same as above).
I can't prove:
- if $p_1 > 2/5$ then $|y_1| = 1$.
Thanks for all kind of help.