Изменения

Из последнего утверждения и шага 2 легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит <tex>L</tex>. Это так, потому что мы создаем ровно L предметов веса <tex>p_{i}</tex> (частота символа). А значит, если в худшем случае мы возьмем все предметы данного веса, то их количество не превысит <tex>L</tex>. Обратите внимание Убедимся также, что одинаковые частоты необходимую сумму (<tex>n - 1</tex>) всегда можно набрать. Зафиксируем размер алфавита равным  <tex>n = 2^k</tex>. Теперь вспомним неравенство, которым связаны  <tex>n</tex> и <tex>L</tex>: <tex> n <= 2^L </tex>. Возьмем минимально возможное значение <tex>L</tex> такое, что <tex>2^L = n</tex>. По условию у разных символов считаются разными,то нас есть. если по <tex>n</tex> монет номинала <tex> p_{2^i} </tex>, где <tex>-L<= p_{j}, i <=-1</tex>. Попробуем посчитать суммарную стоимость имеющихся монет:<tex>n/(2^1) + n/(2^2) + \ne jdots + n / (2^L) </tex>, то при подсчете количества предметов заданного веса мы считаем предеметы с частотой Поскольку <tex>p_{i}n = 2^L</tex> и предметы с частотой :<tex>p_{j}(2^L)/(2^1) + (2^L)/(2^2) + \dots + (2^L) / (2^L) = 2^(L - 1) + 2 ^ (L - 2) + \dots + 2^(L - L) = (2^L) - 1 = n - 1 </tex> отдельноТаким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях L данную сумму гарантированно можно набрать.