Le juste prix

[Médiat]

Bonjour,

Le but du jeu est, pour le joueur B, de trouver le nombre choisi secrètement par le joueur A en posant des questions. Les règles sont les suivantes :

• Le nombre choisi doit être compris entre 1 et 1 000 000.
• Les questions doivent déterminer un sous ensemble de [1 ; 1000000], sans ambiguïté (plus petit/plus grand que par exemple, mais il n'y a pas de limite)
• La réponse ne peut être que oui ou non.

Jusque là pas de problème, en 20 questions tout le monde peut trouver la réponse.

Mais combien de questions faut-il si on ajoute une nouvelle règle :

• Le joueur A est autorisé à mentir une fois (au plus).

La bonne réponse doit donner la stratégie, mais répondre sans justification est possible (ne serait-ce que pour avoir une idée de ce que dit l'intuition).
-----

[Titiou64]

Bonjour,

Réponse bourrin et pas du tout optimisée :

comme on sait que A ne peut mentir qu'une seule fois au maximum, on lui pose chaque question 2 fois. Donc le nombre maximum de question est 40. Après, on peut réduire ce nombre. Si A ment à la première question, on aura 21 questions. De manière plus générale, on a nb de questions = 20 + n avec n le numéro de la question à laquelle A a menti.

[Médiat]

Bonjour,

Je vous confirme que 40 est un majorant, mais on peut faire mieux.

[acx01b]

j'ai 27

 Cliquez pour afficher

Si on pose les 20 questions consistant à demander l'écriture binaire du nombre, on se retrouve avec l'écriture en binaire du nombre mais où l'un des bits peut être faux. Il faut donc ensuite vérifier cette écriture binaire. Pour ça on peut localiser le possible bit faux par dichotomie :
les 20bits s'ont-ils bons ? s'il répond oui c'est terminé. s'il répond non, alors soit il a déjà menti une fois et il est vrai que l'un des bits est faux, soit les 20 bits sont bons et il vient de mentir. On peut alors redemander, les 20bits s'ont-ils bons ? s'il répond oui c'est terminé. s'il répond non, alors on continue
les 10 premiers bits sont-ils bons ? s'il répond non c'est que le bit faux est dans les 10 derniers bits,
etc on localise ainsi le bit faux en ... 5 questions ? Ce qui fait un total de 27 questions dans le pire cas ?

et je n'ai pas fait le cours "codes correcteurs" dont je ne sais pas s'il y a mieux, je pense que oui ?

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

On peut faire mieux

[acx01b]

https://fr.wikipedia.org/wiki/Code_d...g#Code_parfait

 Cliquez pour afficher

25

car n=20,k=25, delta=3
delta =3 car c'est un code de Hamming ce qui permet de résoudre 1 erreur

par contre je ne sais pas encore construire la fonction injective et linéaire

enfin je sais qu'elle existe, donc je peux toujours construire telle que la distance de Hamming soit au minimum de 3,
mais bon le codage et le décodage seront un peu fastidieux puisqu'il faudra générer cette fonction qui est compliquée. Un indice sur une fonction facile à construire ?

[Médiat]

Un seul mot :

 Cliquez pour afficher

Pour plus d'explications : une recherche Google sur "Renyi-Ulam Game".

En particulier : A Solution to Ulam’s Problem with Error-correcting Codes

[obi76]

Bonjour,

Je vous confirme que 40 est un majorant, mais on peut faire mieux.

J'aurai dit 41. Si à la même question on a deux réponses différentes, il faut la reposer une 3° fois pour savoir quelle réponse est correcte...