Код Хаффмана

[main.c]

Всем доброго времени суток. Такой вот вопрос.
Имеется произвольный код Хаффмана, "произвольный" означает, что мы можем выбирать любой алфавит $A$ и приписывать его буквам любые частоты.

Отсортируем кодовые слова произвольного бинарного кода Хаффмана по возрастанию их длины. $L_1 $ – длина самого короткого слова. $L_i $ – длина i-го кодового слова.
Вопрос: насколько малой может быть величина $d_1 = L_2 - L_1$ и можем ли мы для любого фиксированного числа $m$ так выбрать число букв в алфавите $A$ и их частоты, чтобы $d_1$
было больше, чем $m$?
Ответ на первый вопрос элементарный, $d_1$ может быть равно $0$, но не меньше. А вот на второй вопрос я ответить затрудняюсь. Просьба хотя бы дать наводку.

[EtCetera]

Если не ошибаюсь, то можно взять алфавит из $1+2^m$ символов, частоты которых $p_k=2^{-m}$ ($k=1\ldots 2^m$), $p_{m+1}=\dfrac{1}{2}$.

[main.c]

EtCetera в сообщении #656236 писал(а):

Если не ошибаюсь, то можно взять алфавит из $1+2^m$ символов, частоты которых $p_k=2^{-m}$ ($k=1\ldots 2^m$), $p_{m+1}=\dfrac{1}{2}$.

Вы наверное имели ввиду $p_k=2^{-(m+1)}$ ($k=1\ldots 2^m$)?

[EtCetera]

Да, разумеется. В этом случае $d_1$ как раз будет равно $m$.

[main.c]

А не могли бы вы объяснить, почему $d_1$ равно $m$?

[EtCetera]

Найдите длины кодовых слов для всех символов, и узнаете.

[main.c]

Хорошо, в этом я убедился, а допустим в выбранном нами коде Хаффмана $s$ слов. Какие значения может принимать
величина $d_2 = L_s - L_{s - 2}$?

[main.c]

Можно с уверенность сказать, что $L_s$ и $L_{s-1}$ одинаковой длины, причём различаются они лишь последней цифрой, а вот про $L_s$ и $L_{s-2}$ сказать что-то трудно, по идее она может принимать значения $0$ и $1$, но "по идее" это не доказательство, а как это доказать, я пока что себе не представляю.

[EtCetera]

Больше 1 величина $d_2$, очевидно, быть не может. Единица достигается всегда (берем 2 символа с частотой $2^{-(s-1)}$, у остальных частоты равны $2^{-k}$, $k=1\ldots s-2$). Нолик может быть, а может и не быть. Например, при $s=3$ нолик не достигается, а при 4 $\text{---}$ достигается. Когда и почему, неплохо бы разобраться.