Encoder un nombre avec du bruit

[chaube9]

Bilbo, Gandalf et Nitzan jouent au jeu suivant. Tout d'abord, Nitzan choisit un nombre entier entre 1 et 2 ^ (2022) inclus et le révèle à Bilbo. Bilbo compile maintenant une chaîne de longueur 4044 construite à partir des trois lettres a,b et c. Nitzan regarde la chaîne, choisit l'une des trois lettres a, b et c, et supprime de la chaîne toutes les instances de la lettre choisie. Ce n'est qu'alors que la chaîne est révélée à Gandalf. Il doit maintenant deviner le nombre que Nitzan a choisi.

Bilbo et Gandalf peuvent-ils travailler ensemble et trouver une stratégie à l'avance qui permettra toujours à Gandalf de deviner correctement le numéro de Nitzan, peu importe comment il agit ?

[GaBuZoMeu]

Bonjour,

Bilbo écrit le nombre moins un en binaire sur 2022 bits. Puis il ajoute un 2 après chaque bit (0 ou 1) à partir du premier 1, et ajoute devant autant de 0 qu'il faut pour obtenir une chaîne de 4044 caractères. Cette chaîne commence donc par un certain nombre de 0 (éventuellement aucun) puis un 1 puis un 2, sauf si le nombre moins un est zéro auquel cas on n'a que des 0. Gandalf pourra alors facilement décoder la chaîne transmise, quel que soit le choix d'effacement (0, 1 ou 2) de Nitzan.