Si fueran 128 personas, se codificarían todas con palabras de código de largo 7, lo cual alcanzaría exactamente la entropía.
Como son 129, alguna debe recibir una palabra de código de largo mayor a 7 (por Kraft). De hecho vimos que tiene que haber al menos 2 palabras de código hermanas de largo máximo (mayor a 7), digamos z0 y z1.
Se puede ver que en un código óptimo no puede haber ninguna palabra de largo 6: supongamos por el contrario que w tiene largo 6; entonces podemos reemplazar w por w0, z1 por w1, y z0 por z, obteniendo un código de prefijo con menor largo esperado. Más en general, para una distribución uniforme, la diferencia de largo entre palabras de código no puede ser mayor que 1, porque de lo contrario, aplicando exactamente este mismo argumento con una palabra de largo mínimo w y dos hermanas de largo máximo z0 y z1 se llega a una contradicción.
Por lo tanto, en el caso particular de este ejercicio tiene que haber palabras de código de largo 7 y de largo 8. Para minimizar el largo esperado hay que minimizar la cantidad de palabras de largo 8, usando la mayor cantidad posible de largo 7.
Como son 129, alguna debe recibir una palabra de código de largo mayor a 7 (por Kraft). De hecho vimos que tiene que haber al menos 2 palabras de código hermanas de largo máximo (mayor a 7), digamos z0 y z1.
Se puede ver que en un código óptimo no puede haber ninguna palabra de largo 6: supongamos por el contrario que w tiene largo 6; entonces podemos reemplazar w por w0, z1 por w1, y z0 por z, obteniendo un código de prefijo con menor largo esperado. Más en general, para una distribución uniforme, la diferencia de largo entre palabras de código no puede ser mayor que 1, porque de lo contrario, aplicando exactamente este mismo argumento con una palabra de largo mínimo w y dos hermanas de largo máximo z0 y z1 se llega a una contradicción.
Por lo tanto, en el caso particular de este ejercicio tiene que haber palabras de código de largo 7 y de largo 8. Para minimizar el largo esperado hay que minimizar la cantidad de palabras de largo 8, usando la mayor cantidad posible de largo 7.