Principe de Dichotomie

[invite01b26842]

Bonjour,

-Posons une echelle de 0 à 100
-Une personne choisit un nombre x dans sa tete
-"Le but" est de trouver se nombre en moins de coups possible ....(pour le moment rien de plus bateau)

-"Le principe" le plus avantagueux sereais donc celui de la dichotomie, c'est a dire de donner toujours le nombre intermediaire entre l'echelle restante ...
EX: Admettons que x=73 (mais n'en tenons pas compte)
L'echelle est donc de 0 à 100, prenons 50, puis 75, puis 63,puis 69,puis 72 et enfin 73


Enfin comment expliquer que l'on obitnet en maximum 6 coups ?
-----

[SunnySky]

J'imagine qu'à chaque essai, on nous informe si le nombre à trouver est inférieur ou supérieur à notre essai?

Même dans ce cas, il est possible d'avoir besoin de 7 essais. Par exemple: le nombre à trouver est 1. On aura les essais suivants: 50-25-13-7-4-2-1.

Pour être sûr de trouver au dernier essai, il ne doit rester que 1 possibilité. Cela signifie qu'à l'avant-dernier essai, il n'y a pas plus de 2 possibilités. Au tour précédent, il n'y avait donc qu'un maximum de 4 possibilités. Le tour d'avant: maximum 8 possibilités. Les tours précédents: 16, 32, 64, 128.

Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique.

[danyvio]

Enfin comment expliquer que l'on obtient en maximum 6 coups ?

J'ai eu le plaisir de programmer moult algo de recherche. Le principe est simple :
Il suffit d'éliminer à chaque tour la moitié du reste. Comment ?
D'abord, il faut que les éléments parmi lesquels on recherche soit TRIéS (important). On propose l'élément de milieu. En fonction de la réponse, on élimine ce qui est plus grand, ou plus petit, c'est à dire la moitié du reste.
SUpposons qu'on recherche 720 parmi 1023 on proposera successivement :

(1+1023/ / 2 soit 512 réponse : trop petit on élimine 1 à 512 il reste 513 à 1023
On propose (513+1023) / 2 soit 768 réponse : trop grand, on élinmine 768 à 1023, il reste 513 à 767.
On propose (513+767) / 2 soit 640 réponse : trop petit on élimine 513 à 640 il reste 641 à 767.

On propose (641+767) / 2 soit 704 réponse : trop petit, on élimine 641 à 704 il reste 705 à 767.
On propose (705+767) / 2 soit 736 réponse : trop grand on élimine 736 à 767 il reste 705 à 735.
On propose (705+735) /2 soit 720 TROUVé !

En conclusion, le nombre de recherches est, au maximum, = à log (de base 2) du nombre d'éléments, puisuqe à chaque itération on élimine la moitié du reste.

[yat]

J'imagine qu'à chaque essai, on nous informe si le nombre à trouver est inférieur ou supérieur à notre essai?

Même dans ce cas, il est possible d'avoir besoin de 7 essais. Par exemple: le nombre à trouver est 1. On aura les essais suivants: 50-25-13-7-4-2-1.

Pour être sûr de trouver au dernier essai, il ne doit rester que 1 possibilité. Cela signifie qu'à l'avant-dernier essai, il n'y a pas plus de 2 possibilités. Au tour précédent, il n'y avait donc qu'un maximum de 4 possibilités. Le tour d'avant: maximum 8 possibilités. Les tours précédents: 16, 32, 64, 128.

Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique.

En fait je ne sais pas comment tu fais tes comptes. Si je suis ton raisonnement, au premier essai on peut avoir 128 possibilités, 64 au 2ieme, 32 au 3ieme, 16 au 4ieme, 8 au 5ieme, 4 au 6ieme, 2 au 7ieme, et ce n'est qu'au 8ieme essai qu'on est sur de trouver la solution (Je reprends tes valeurs). D'ailleurs tu peux essayer ta méthode avec la réponse 0 : comme on te répondra toujours "c'est moins", tu vas faire les mêmes propositions qu'avec le 1 sauf qu'à la fin tu n'auras pas trouvé. Il te faudra donc effectivement un 8ieme essai pour proposer le zéro.

Une deuxième erreur dans ton raisonnement te fait retomber sur le bon résultat quand même : tu oublies qu'à chaque étape ou la réponse n'est pas trouvée, on élimine l'élément choisi. L'ensemble n'est donc pas exactement coupé en deux.

Concrètement, pour trouver au dernier essai, en effet il faut qu'il ne reste qu'une possibilité, mais pour cela on peut avoir encore trois possibilité à l'étape précédente. Puis 7, 15, 31, 63 et 127. A un élément près, tu as donc toujours une étape de retard. Mais il faut bien 7 étapes maximum pour un ensemble de 127 éléments.

Pour des entiers de 0 à 100, si on me répond toujours "c'est moins", la série de propositions sera, au pire : 50, 25, 12, 6, 3, 1 et 0.

[A voir en vidéo sur Futura]

[SunnySky]

Bien vu! En effet, je me suis un peu trompé. Mais peut-être pas autant que tu le dis.

Je disais qu'avec 7 essais, on pouvait trouver n'importe quel nombre jusqu'à 128 car 2⁷=128, il y a donc 128 possibilités. Mais bien sûr, cela suppose implicitement que 0 est exclus: si on accepte le 0, on a 129 nombres différents entre 0 et 128. Si on accepte le zéro, alors j'aurais dû dire qu'il fallait arrêter à 127. Vouloir à tous prix me défendre, je pourrais bien dire que je précisais: Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique. Mais ce serait un peu malhonnête de ma part car je je n'y avais pas pensé du tout.

Par contre, pour le reste, je crois avoir raison. Si tu choisis un nombre compris entre 1 et 128 (inclus...), je crois que je pourrai toujours le trouver en 7 coups. Par contre, de 1 à 129, je ne suis pas sûr d'y arriver.

Si j'essaie d'expliquer mon raisonnement avec ta formulation, je dirais ceci: Avant mon premier essai, il y a 128 possibilités, mais après, il y en a 64. Après mon deuxième essai, il reste 32 possibilités. Il en reste 16 après le troisième, 8 après le quatrième, 8 après le quatrième, 4 après le cinquième, 2 après le sixième et par conséquent, les septième et huitième essais doivent nécessairement permettre de trouver la bonne réponse.

Je reste toutefois sensible à ton argument selon lequel l'ensemble n'est pas exactement coupé en deux. Mais je n'arrive pas à l'exploiter de façon à résoudre un problème à 129 possibilités. Par exemple, si on choisit un chiffre entre 1 et 129, (disons le 64), on aura: 65, 32, 48, 56, 60, 62, 63, 64 et donc huit essais. J'ai besoin d'y réfléchir encore un peu.

[yat]

Bien vu! En effet, je me suis un peu trompé. Mais peut-être pas autant que tu le dis.

Sauf ton respect, la suite de ce message confirme que si

Je disais qu'avec 7 essais, on pouvait trouver n'importe quel nombre jusqu'à 128 car 2⁷=128, il y a donc 128 possibilités. Mais bien sûr, cela suppose implicitement que 0 est exclus: si on accepte le 0, on a 129 nombres différents entre 0 et 128. Si on accepte le zéro, alors j'aurais dû dire qu'il fallait arrêter à 127. Vouloir à tous prix me défendre, je pourrais bien dire que je précisais: Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique. Mais ce serait un peu malhonnête de ma part car je je n'y avais pas pensé du tout.

Quand bien même... le problème n'est pas là. Pour être sur de trouver en 7 essais, il faut que l'ensemble contienne 127 éléments. Pas 128. Donc de 1 à 128 ou de 0 à 127, ça ne marche pas. C'est 0 à 126 ou 1 à 127. La banane est quand tu dis qu'on peut trouver n'importe quel nombre jusqu'à 128 car 2⁷=128. En effet, tu calcules ainsi le nombre d'étapes nécessaires pour connaitre le nombre, avec une division par 2 à chaque étape. Mais tu oublies qu'après l'avoir déterminé il faut encore utiliser un essai pour l'annoncer. Par exemple s'il te reste deux nombres possibles, tu peux très bien avoir besoin de deux essais pour donner le bon : il suffit de te tromper au premier essai. Donc en partant comme tu le fais sur une division par 2 de l'ensemble à chaque étape, on retombe bien sur les explications que tu donnais précédemment :

Pour être sûr de trouver au dernier essai, il ne doit rester que 1 possibilité. Cela signifie qu'à l'avant-dernier essai, il n'y a pas plus de 2 possibilités. Au tour précédent, il n'y avait donc qu'un maximum de 4 possibilités. Le tour d'avant: maximum 8 possibilités. Les tours précédents: 16, 32, 64, 128.

Et dans ces explications, y a pas à tortiller, si tu en déduis qu'il faut 7 étapes c'est tout simplement que tu as mal compté, il en faut 8. Donc au lieu de 1, 2, 4, 8, 16, 32, 64, 128, il faut dire 1, 3, 7, 15, 31, 63, 127. Et tu gagnes une étape, on retombe bien sur les 7 étapes nécessaires pour un ensemble d'au plus 127 éléments.

Par contre, pour le reste, je crois avoir raison. Si tu choisis un nombre compris entre 1 et 128 (inclus...), je crois que je pourrai toujours le trouver en 7 coups. Par contre, de 1 à 129, je ne suis pas sûr d'y arriver.

Alors allons-y, je pense à un nombre entre 1 et 128 inclus, je te mets au défi de le trouver en 7 coups
Pour accélérer un peu le processus et éviter d'avoir 8 allers-retours à faire, je te donne mon algorithme : je compte combien d'éléments de l'ensemble sont strictement supérieurs à ta proposition, combien sont strictement inférieurs. Si c'est égal, je reponds au hasard. Si l'un est plus grand que l'autre, alors je te branche sur le plus grand ensemble des deux. Par exemple, à la première étape, on a 128 éléments de 1 à 128. Si tu proposes 64 alors on a 63 éléments inférieurs et 64 supérieurs. Je réponds donc "c'est plus". Par contre, si tu proposes 65, alors je répondrai "c'est moins". Dans le premier cas, il te reste 64 éléments de 65 à 128... là encore, tu as un nombre pair d'éléments, donc tu ne peux pas te retrouver avec deux ensembles égaux à l'étape suivante. Si tu dis 96, tu as 31 éléments inférieurs, 32 supérieurs. Je dis donc "c'est plus". Et même si tu joues parfaitement, tu auras toujours un des deux ensembles qui aura exactement la moitié de la taille du précédent, ce qui t'amène donc à 16 possibilités après la 3ieme étape, 8 après la 4ieme, 4 après la 5ieme, 2 après la 6ieme, donc pour ta 7ieme proposition, tu auras toujours le choix entre ces deux possibilités. Comme naturellement tu vas te tromper, il te faudra un 8ieme essai pour gagner.

Si j'essaie d'expliquer mon raisonnement avec ta formulation, je dirais ceci: Avant mon premier essai, il y a 128 possibilités, mais après, il y en a 64. Après mon deuxième essai, il reste 32 possibilités. Il en reste 16 après le troisième, 8 après le quatrième, 8 après le quatrième, 4 après le cinquième, 2 après le sixième et par conséquent, les septième et huitième essais doivent nécessairement permettre de trouver la bonne réponse.

Oui, oui, c'est exactement comme ça que j'ai formulé ton raisonnement hier. 128 possibilités => 8 essais pour trouver. Quel est ton propos exactement ?

Je reste toutefois sensible à ton argument selon lequel l'ensemble n'est pas exactement coupé en deux. Mais je n'arrive pas à l'exploiter de façon à résoudre un problème à 129 possibilités. Par exemple, si on choisit un chiffre entre 1 et 129, (disons le 64), on aura: 65, 32, 48, 56, 60, 62, 63, 64 et donc huit essais. J'ai besoin d'y réfléchir encore un peu.

Tu n'as pas du bien lire mon post précédent. Pour un problème à 129 possibilités, il faut 8 essais au maximum. Pareil pour un problème à 128 possibilités. C'est uniquement à partir de 127 possibilités qu'on sera sur de s'en sortir en 7 essais.

De manière un peu plus formelle, la démo : admettons qu'il faut au plus n essais pour trouver un élément dans un ensemble de 2ⁿ-1 éléments.

Si on a un ensemble qui contient 2ⁿ⁺¹-1 éléments, en choisissant l'élément médian on sépare l'ensemble en trois parties : l'élément médian et deux parties de 2ⁿ-1 éléments (2ⁿ-1 + 2ⁿ-1 + 1 = 2ⁿ⁺¹-1).
Si la réponse est "c'est ça", alors on aura trouvé en 1 essai. Si c'est "c'est plus" ou "c'est moins", alors on aura dépensé un premier essai, il reste à trouver la solution dans un sensemble de 2ⁿ-1 éléments. Or pour cela il faut au plus 2 essais, donc si l'ensemble contient 2ⁿ⁺¹-1 éléments, il faudra au plus n+1 essais.

Pour un ensemble d'un élément, il faut au plus un essai pour trouver la solution, donc la propriété est vraie pour n=0...

Pour tout n entier positif, il faut donc au plus n essais pour trouver la solution dans un ensemble de 2ⁿ-1 éléments.


Et maintenant, je démontre qu'il n'est pas possible d'être sur de trouver en n essais un élément parmi 2ⁿ : pour n=1, il n'est pas possible de trouver en un essai un élément parmi deux. C'est fini.

[SunnySky]

J'ai besoin d'y réfléchir encore un peu.

Je ne regrette pas d'avoir écrit cette ligne...

En effet, ton algorithme m'a convaincu. Ce qui m'avais distrait, dans ton message précédent, c'était que tu avais pris zéro, nombre que je n'acceptais pas. Du coup, ayant trouvé un os, je croyais que c'était le seul. Erreur...

Et je comprends mieux la division en sous-ensembles égaux produite par un nombre impair de possibilités initiales.

Bref, c'est un peu pénible pour mon orgueil, mais je te donne raison sur toute la ligne...

[inviteb86f5e9f]

c'est l'alternance de valeurs paires et impaires qui fait que selon les limites données au départ, on commence par une valeur paire ou impaire c'est à dire que l'on peut diviser en deux parties égales ou non.
Ce que je veux dire c'est que si on dit entre 0 et 100 inclus, il y a 101 valeurs et le but est donc d'enlever celle du milieu pour qu'il nous reste deux "lots" identiques je vais donc prendre 50 et il restera donc de 0 à 49 soit 50 valeurs et de 51 à 100 soit aussi 50 valeurs. Par contre au coup suivant quel que soit la réponse il y aura un nombre pair que je vais devoir donc diviser en deux parties forcément inégales!... et il y en aura une paire et l'autre impaire quel que soit mon choix
Ce choix aurait pu intervenir dès le départ si l'on donne comme limite de 1 à 100 car nous avons 100 possibilités soit un nombre pair de valeur. Et je peux choisir soit 50 dans ce cas il restera de 1 à 49 = 49 valeurs et de 51 à 100 soit 50 valeurs. Mais je peux aussi choisir 51 et dans ce cas c'est l'inverse : nous avons 50 valeur de 1 à 50 et 49 de 52 à 100.
C'est ce deuxième choix qui est préférable dans le cas où c'est un matheux qui vous propose ce jeu en effet pensant que vous allez choisir 50 qui vient naturellement à l'esprit