29
правок
Изменения
м
Нет описания правки
#:Пусть у нас есть <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> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен:
#: <center><tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{-l_1}} + \dfrac{1}{r^{-l_2}} + \ldots + \dfrac{1}{r^{-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></center>#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i \in \mathbb{N}, r \in \mathbb{N} </tex>. Следовательно числитель натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма: <tex> \sum\limits_{j = 1}^{i} r ^{-l_j} \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.#У Пусть у всех слов из одной группы будет одна и та же начальная буква<tex> \Rightarrow</tex> ''у каждой группы своя начальная буква''. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен.
#:'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна.
