Por qué no existe el compresor perfecto o los nidos de las palomas

Supongamos que existe un compresor que toma cualquier cadena de bits y la comprime en otra cadena con menos bits. Llamaremos $c(x)$ al algoritmo compresor y $d(x)$ al descompresor.

Está claro que

$$c(0)=\epsilon$$

Puesto que la cadena vacía $\epsilon$ es la única cadena con menos longitud que la cadena $0$. ¡Pero también es inmediato para la cadena $1$!

$$c(1)=\epsilon$$

Entonces, ¿cuánto es $d(\epsilon)$? Porque sólo podrá ser una de las dos cadenas iniciales, pero no las dos.

Esto es el llamado principio del palomar. Sólo tenemos una cadena de longitud cero para almacenar dos cadenas de longitud uno. Si en un palomar hay más pichones que nidos, en algún nido habrá dos pichones (y no podremos descomprimirlos).

Por tanto, no existe el compresor perfecto. Habrá cadenas que comprima y otras que expanda. El truco está en que comprima las cadenas más usadas y expanda las menos usadas.