Énoncé:
Soit $A$ et B des chaînes de bits (séquences de $0$ et de $1$).
Si $A$ est égal aux longueur($A$) bits les plus à gauche de $B$, alors on dit que $A$ est un préfixe de $B$.
Par exemple, $00110$ est un préfixe de $001101001$, mais pas de $00111$ ou $100110$.
Un code sans préfixe de taille $n$ est une collection de $n$ chaînes de bits distinctes telles qu'aucune chaîne n'est un préfixe d'une autre. Par exemple, voici un code sans préfixe de taille 6:
$$0000, 0001, 001, 01, 10, 11$$
Supposons maintenant que la transmission d'un bit "$0$" coûte un penny, mais que la transmission d'un "$1$" coûte quatre pennys.
Dans ce cas, le coût total du code sans préfixe présenté ci-dessus est de $35$ pennys, ce qui se trouve être le moins cher possible pour le schéma de tarification en question.
En bref, nous écrivons Coût($6$)$ = 35$.
Combien vaut Coût$(10^9)$ ?
Lien du problème originel