Изменения

*#: Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> .

#: Пусть у нас есть <tex>n</tex> символов, кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. Давайте разделим данные символы на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{----l_i} \leqslant \dfrac{1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса.

Пусть у нас есть <tex>n</tex> символов*Докажем, что в таком случае группа будет либо полностью укомплектована, кодовые слова которого имеют длины либо будут исчерпаны все возможные <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n l_i </tex>. Давайте разделим данные символы на <tex>r</tex> группЭто следует из того, внутри каждой из которых что при <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{geqslant 1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i i</tex> в порядке увеличения индекса. -ом шаге либо группа уже укомплектована, либо ее остаток равен:

Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <texcenter> l_i </tex> . Это следует из того, что при <tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{l_i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \geqslant ldots + r^{l_i - l_{i - 1 }} )}{r^{l_i}}</tex> на <tex>i</texcenter>-ом шаге либо группа уже укомплектована, либо ее остаток равен:

*Так как группа не укомплектована, то числитель положителен. Если добавим <centertex>l_i </tex> в группу, то числитель уменьшится на <tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{</tex>. Тогда, взяв <tex> l_i-1}} \right ) = \dfrac{r^{l_{i-1}} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex>в группу, мы не перепрыгнем через максимальное значение. А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</centertex>групп, удовлетворяющих условию.

Так как группа не укомплектована#: Для доказательства достаточности опишем рекурсивную процедуру, то числитель положителен. Если добавим которая строит код для данного набора длин <tex> l_i </tex> в группу, то числитель уменьшится на удовлетворяющих неравенству <tex>\sum\limits_{i = 1</tex>. Тогда, взяв <tex> }^{n} r ^{-l_i } \leqslant 1 </tex> в группу, мы не перепрыгнем через максимальное значение. А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.

#: Разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{----l_i} \leqslant \dfrac{1}{r} </tex> . Разделить длины на группы будем алгоритмом описанным выше. У всех слов из одной группы будет одна и та же начальная буква.

Для доказательства достаточности опишем рекурсивную #: Запуститим данную процедуру, которая строит код для данного набора длин <tex> l_i </tex> каждой группы слов, удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex> предварительно обрезав первую букву.

*Разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить длины на группы будем алгоритмом описанным выше. У всех слов из одной группы будет одна и та же начальная буква.  *Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву. #: Доказательство корректности проведём по индукции по величине <tex> l_n </tex> .