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.
J'ai du mal à réfléchir mais la procédure suivante n'est-elle pas plus rapide ?
1. Le nombre X recherché peut s'écrire X = Q*7 + R.
2. Poser la question: Quel est le reste de la division par 7? On connaît R
3. Q est largement inférieur à 143. J'imagine qu'il faut moins de 8 questions par dichotomie pour le trouver, non ?
Clairement, il y a moyen d'optimiser la procédure pour être plus efficace encore.
# 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 !
# Modulo
Posté par tisaac (Mastodon) . En réponse au journal Déterminer un code à 3 chiffres en 9 questions ou moins. Évalué à -4.
J'ai du mal à réfléchir mais la procédure suivante n'est-elle pas plus rapide ?
1. Le nombre X recherché peut s'écrire X = Q*7 + R.
2. Poser la question: Quel est le reste de la division par 7? On connaît R
3. Q est largement inférieur à 143. J'imagine qu'il faut moins de 8 questions par dichotomie pour le trouver, non ?
Clairement, il y a moyen d'optimiser la procédure pour être plus efficace encore.
Surtout, ne pas tout prendre au sérieux !