Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 23-11-2011 18:27:55

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Masttermind et nombre de questions

Une petite question qui m'a traversé la tête, et dont je crois détenir une réponse universelle :

Comme dans le Mastermind proposé par Clydevil ici, un maître du jeu choisit un nombre entre 1 et N.

Cette fois-ci, un seul joueur répond. Il ne peut poser que des questions auxquelles on répond par oui ou par non. Il pose une question sur le nombre choisi, le MJ répond, etc.

Combien de questions au maximum un joueur supposé "fûté" devra-t-il poser pour trouver la réponse ?

Je ne crois pas que ce soit vraiment difficile, alors amusez-vous bien (j'en connais deux/trois qui auront répondu juste, en deux lignes, d'ici une ou deux heures à peine lol)



Annonces sponsorisées :

Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
  • |
  • Répondre

#0 Pub

 #2 - 23-11-2011 18:41:18

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Mastermind te nombre de questions

Il me semble que k réponses où k est le plus petit entier tel que [latex]2^k\geq N[/latex] est un bon candidat smile

Vasimolo

 #3 - 23-11-2011 18:47:45

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

mastermind et nombre de qurstions

[TeX]roundup(\frac{ln(n)}{ln(2)})[/TeX]


The proof of the pudding is in the eating.

 #4 - 23-11-2011 20:45:35

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3766
Lieu: hébesphénorotonde triangulaire

Mastermind et nombre de questinos

Exprimer la borne supérieure en base 2, puis compter le nombre de digits. Si je ne me trompe pas, ce nombre de digits est la réponse cherchée.

Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #5 - 24-11-2011 09:30:23

Zindy
Passionné de Prise2Tete
Enigmes résolues : 48
Messages : 50

Mastermind et nombre de questons

Si la réponse ne peut être que oui ou non, on a donc une réponse assez "binaire" !!!

Il suffit de regarder la puissance de 2 supérieure à N la plus proche (c'est la valeur K=log2(n) arrondi à l'entier supérieur), et en K questions, on peut trouver le nombre par dichotomie.

Pour les questions, cela revient à demander si chaque bit de la représentation binaire du nombre N vaut 0 ou 1, il faut donc autant de questions que le nombre de bits nécessaires pour représenter n.

Au final, on a donc un oui ou un non pour chaque bit, donc on a tous les bits du nombre N, on connait donc le nombre N.

 #6 - 24-11-2011 09:46:24

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 479
Lieu: Ardèche

mastermond et nombre de questions

[TeX]ceiling\,(\log_2 N)\,?[/TeX]
où ceiling(x) est le plus petit entier supérieur ou égal à x
On procède par dichotomie.
(Il faut n réponses pour distinguer [latex]2^n[/latex] ≥ N  cas)

 #7 - 24-11-2011 11:23:08

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Mastermind et nombre de quetsions

Nickel pour quasiment tout le monde. Ce n'est effectivement pas bien dur smile

@Klimrod : si je ne me trompe pas, tu as une légère erreur. Regarde ce qui se passe pour certaines valeurs "particulières"... (Si tu ne vois pas desquelles je parle, envoie un MP smile)


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #8 - 24-11-2011 11:37:29

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

mastermind et nombre de qurstions

La logique voudrait que l'on réponde log2(n), en procédant par dichotomie.
Cependant, on a vu récemment que pour une question à laquelle on répond par oui ou non, il existe le cas où il n'y a pas de réponse; donc on peut même faire log3(n)

Par exemple, pour trouver un nombre entre 1 et 9; on peut poser 4 questions basiques:
- est il compris entre 1 et 4? non
- est il compris entre 5 et 7? oui
- est il compris entre 5 et 6? oui
- est-ce 5? oui
=> La réponse est 5

mais on peut aussi faire en 2 questions:
- l'ensemble A contient les chiffres de 1 à 3; ne contient pas les chiffres de 7 à 9; quant aux chiffres de 4 à 6 je ne te le dis pas. Le nombre est-il dans A? réponse "?"
- l'ensemble B contient 4 et pas 6; quant à 5 je ne te le dis pas. Le nombre est-il dans B? réponse "?"
=> La réponse est 5

 #9 - 24-11-2011 13:27:10

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

mastermind et nombre de quedtions

Scarta a exploité la faille que je ne voulais pas qu'on cite. Le problème, c'est qu'en rappelant cette faille, je donnais aussi la clé de résolution, et je ne voulais pas le faire.

A un petit quelque chose près (genre, repasser à des nombres entiers), j'accepte ses deux réponses big_smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #10 - 26-11-2011 09:16:21

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,471E+3

mastermind ey nombre de questions

On ne peut éliminer que la moitié des nombres à coup sûr à chaque question, donc je verrais bien

n questions, avec n minimum pour avoir 2^n > N

 #11 - 26-11-2011 14:49:42

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

Mastermind et ombre de questions

Il suffit de calculer le nombre de questions dans mastermind 1 dont tu étais le vainqueur ! lollol
Je n'ai pas assez de temps pour ça !
====> []


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #12 - 27-11-2011 12:21:03

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Mastermind et nombre d questions

gwen27 a écrit:

On ne peut éliminer que la moitié des nombres à coup sûr à chaque question, donc je verrais bien

n questions, avec n minimum pour avoir 2^n >= N

Je récupère cette réponse, qui est d'une limpidité absolue... en changeant le "strictement supérieur" en "supérieur ou égal" néanmoins.

La formulation mathématique brute a été correctement donnée par Franck et Halloduda.

Bravo à tous !


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete