Dichotomie jusqu'à trouver ou atteindre 3 dépassements, puis incrémentation. Lors de la phase de dichotomie, on arrondi à l'inférieur. Pire cas, 11, 14 propositions :
50-25-12-1-2-3-4-5-6-7-8-9-10-11

Bjr titoufred,

Je procéderai par dichotomies successives. Soit X ton nombre secret.
Je te demande 1/ X est-il >= à 50 ?

Si ta réponse 1/ est OUI, je te demande 2/ X est-il >= à 75 ?

Si ta réponse 2/ est OUI, je te demande 3/ X est-il >= à 88 ?

Si ta réponse 3/ est OUI, je te demande 4/ X est-il = à 88 ?

Si ta réponse 4/ est NON, je te demande 5/ X est-il = à 89 ?

Si ta réponse 5/ est NON, je te demande 6/ X est-il = à 90 ?
etc jusqu'à 99, jusqu'à avoir trouvé.

Par contre, ...
Si ta réponse 1/ est NON, c'est mon 1er dépassement,
je te demande 2/ X est-il >= à 25 ?

Si ta réponse 2/ est OUI, je te demande 3/ X est-il >= à 38 ?

Si ta réponse 2/ est NON, 2nd dépassement,
je te demande 3/ X est-il >= à 12 ?

Avec cette méthode, on doit y arriver en une quinzaine d'essais, mais même si c'est sûrement pas le record minimal, il n'y a pas le feu au lac

Si l'on propose une dichotomie classique, c'est assez rapide, en 7 ou 8 coups. On n'a pas le droit de s'en servir ?

En 7 il je ne vais que jusqu'à 98 , il me faut donc un 8 ème coup...

Mais connaître la réponse à l'énigme que tu mentionnes ne suffit pas...

Mouarf ça dépend ce que veut dire connaître ;p  il y a "mal connaître" et il y a avoir résolu pour n sphères de cristal (ce qui n'est pas nécessairement plus dur comme récurrence), quand n tend vers l'infini le protocole tendra vers une simple dichotomie, pour un n quelconque c'est une structure fractale non symétrique.
Je l'avais résolu pour n quelconque, ici n=3, malheureusement j'ai perdu mes notes et suis du genre extrêmement flemmard :p.
Cela dit, énigme très intéressante! c'est beau de voir qu'avec des énoncés simples on peut avoir des structures déjà complexes.

@nodgim : on ne peut pas faire une dichotomie classique car on n'a le droit qu'à 3 erreurs de dépassement.

"Attention, si une proposition dépasse le nombre mystère, cela compte comme une erreur nommée dépassement"


Peut-on poser des questions du genre "1°) TON NOMBRE EST-IL PAIR ?" ?
ou  "2°) TON NOMBRE EST-IL MULTIPLE DE TROIS ?"
ou  "3°) LE LOGARITHME DE TON NOMBRE EST-IL SUPÉRIEUR À 2 ?"

Si oui, ça pourrait (?) permettre d'élaguer les possibilités...

@Clydevil : Oui, c'est ça mais avec nTry==0 pour le deuxième test.

C'est ca la différence en fait avec le truc des sphère de cristal, c'est que dans le cas des sphères on doit aller jusqu'au dépassement pour déterminer que c'est l'étage fatidique, alors que la ca dit "trouvé" avant

En effet, petite nuance, au temps pour moi.

On pourrait deviner un nombre mystère compris entre 1 et 162 avec 8 propositions.

Je confirme et on commence en 93.

Merci pour cette variante.

@Rivas :

voici ton exemple donné pour 97 :

Spoiler : [Afficher le message] 33, 55, 70, 85, 92, 96, 98(*), 97

si je suis la stratégie que tu as énoncée, il me semble que 73 nécessite 9 propositions non ?

Spoiler : [Afficher le message] 33, 55, 70, 85(*), 78(**), 74(***), 71, 72, 73.

Première constatation, arrivé à 3 erreurs de dépassements, il faut commencer en bas de la plage des possibilités restantes et remonter de 1 en 1, on est ainsi sûr de trouver la réponse sans un quatrième dépassement. Du coup, si jamais il reste N nombres dans la plage des possibilités restantes, il faut donc au pire-cas N tentatives pour tomber dessus. Il faut donc minimiser le nombre de possibilités restantes à l'issue des 3 erreurs.

Autrement dit, une fois qu'on a eu nos 3 dépassements, il faut bourrinement balayer tous les cas restant, alors que tant qu'il nous reste des possibilités d'erreur, on peut taper par pallier.

La dichotomie n'est pas la meilleure solution, car si on propose 50 en premier choix, selon qu'on est en dépassement ou non, il nous reste en gros 50 cas possibles à étudier, sauf que dans un des cas, on n'a plus que deux "cartouches dépassement" à user pour resserrer les choix parmi 50, alors que dans l'autre cas, il nous reste 3 "cartouches dépassement" possibles toujours pour resserrer les choix parmi 50.

Il aurait donc mieux valu que dans le cas où on dépasse, il nous reste moins de cas que dans l'autre. Il faut donc que toute proposition laisse moins de cas possibles si on dépasse que si on ne dépasse pas.

D'où l'idée suivante : dans la plage des nombres possibles, proposer toujours le nombre qui marque le seuil du premier tiers de cette plage. Exemple, au départ, la plage couvre entre 1 et 99, on proposera donc 33 (le tiers de 99).
Là, si on dépasse, on sait que la solution est entre 1 et 32, on refait une proposition au tiers donc on propose 11 (le tiers de 32 arrondi sup).
Et si on ne dépasse pas, on sait que la solution est entre 34 et 99 (donc il reste 66 possibilités, mais on n'a toujours pas "grillé" de cartouche "erreur"), et on proposera 55 (seuil du premier tiers de la plage 34-99).

Le pire-cas correspond alors au nombre 99, qui nécessite 10 essais. C'est le pire-cas puisque ne tombant jamais sur une erreur, on ne réduit jamais le nombre de possibilités au tiers des possibilités restantes.

Les propositions sont alors : 33 OK, 55 OK, 70 OK, 80 OK, 87 OK, 92 OK, 95 OK, 97 OK, 98 OK, 99 FIN

Si on prend par exemple 69 (exemple complètement au hasard), voici le cheminement en 8 coups avec cette stratégie : 33 OK, 55 OK, 70 ERR, 60 OK, 64 OK, 66 OK, 68 OK, 69 FIN

@nodgim :
C'est comme le nombre mystère habituel, on te répond "plus grand", "trouvé" ou "plus petit". Sauf que tu n'as le droit d'entendre que 3 "plus petit". A la 4ème proposition dépassant le nombre mystère, tu as perdu.

@rivas : je suppose que ta solution marche comme ça oui. bravo. Elle permet de trouver le nombre mystère en Spoiler : [Afficher le message] 8 coups maximum.

Cependant, il y a une stratégie qui permet de trouver le nombre mystère en moins de coups que la tienne en moyenne.

Faire une proposition, c'est proposer un nombre.