Pas certain, mais il me semble qu'en fait il n'y a pas moyen de faire mieux que l'algorithme (par dichotomie) proposé pour garantir une réponse en 10 questions.
En effet, vu que la réponse est oui ou non; chaque question permet de diviser en 2 parties (pas forcément égales) le reste des candidats possibles (indépendamment des questions précédentes).
Si on prend une approche telle que proposée qui divise en deux parties égales le reste des candidats, on est sur de trouver la réponse en 10 étapes (pas 9 ni 11). On est donc sur de ne pas obtenir le bonus.
Si on ne divise pas l'ensemble des candidats en deux parties égales, l'algorithme peut terminer plus rapidement qu'en 9 étapes mais peut être beaucoup plus lent. Exemple extrême: l'énumération:
- Est-ce 000 ?
- Est-ce 001 ?
- ...
Avec de la chance vous pouvez terminer en moins de 9 étapes, avec pas de chance,...
Autre exemple, si vous posez une question comme
- Y a-t-il un nombre pair ou plus dans la combinaison ?
Si la réponse est non, vous n'avez plus que 125 candidats restants (vous avez de la chance)
Si non, il vous en reste 875 :-(
Pour conclure, il n'y avait pas moyen d'être sur d'obtenir le bonus mais l'approche que vous aviez choisi vous garantissait de ne pas l'obtenir.
# Début de preuve
Posté par tisaac (Mastodon) . En réponse au journal Déterminer un code à 3 chiffres en 9 questions ou moins. Évalué à 10.
Pas certain, mais il me semble qu'en fait il n'y a pas moyen de faire mieux que l'algorithme (par dichotomie) proposé pour garantir une réponse en 10 questions.
En effet, vu que la réponse est oui ou non; chaque question permet de diviser en 2 parties (pas forcément égales) le reste des candidats possibles (indépendamment des questions précédentes).
Si on prend une approche telle que proposée qui divise en deux parties égales le reste des candidats, on est sur de trouver la réponse en 10 étapes (pas 9 ni 11). On est donc sur de ne pas obtenir le bonus.
Si on ne divise pas l'ensemble des candidats en deux parties égales, l'algorithme peut terminer plus rapidement qu'en 9 étapes mais peut être beaucoup plus lent. Exemple extrême: l'énumération:
- Est-ce 000 ?
- Est-ce 001 ?
- ...
Avec de la chance vous pouvez terminer en moins de 9 étapes, avec pas de chance,...
Autre exemple, si vous posez une question comme
- Y a-t-il un nombre pair ou plus dans la combinaison ?
Si la réponse est non, vous n'avez plus que 125 candidats restants (vous avez de la chance)
Si non, il vous en reste 875 :-(
Pour conclure, il n'y avait pas moyen d'être sur d'obtenir le bonus mais l'approche que vous aviez choisi vous garantissait de ne pas l'obtenir.
Surtout, ne pas tout prendre au sérieux !