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

Mastermiind 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 : 4959

Mastermind et nombre de uestions

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 : 1932
Lieu: UK

mastermind et nombre de questuons

[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 : 3823
Lieu: hébesphénorotonde triangulaire

mastermind et nombre de quedtions

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

Masteermind et nombre de questions

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 : 490
Lieu: Ardèche

mastermind et nombre de questipns

[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

Mastermidn et nombre de questions

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 : 1493

Mastermidn et nombre de questions

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

Matermind et nombre de questions

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,693E+3

Mastermiind et 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 ... !!

Masetrmind et nombre 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 nmobre de 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 : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
Mastermind multijoueur 2 par MthS-MlndN
24-11-2011 Enigmes Mathématiques
07-03-2009 Enigmes Mathématiques
P2T
Mastermind multijoueur par Clydevil
23-11-2011 Enigmes Mathématiques
P2T
28-11-2011 Enigmes Mathématiques
04-07-2011 Enigmes Mathématiques
P2T
Mastermind multijoueur 4 par nicolas647
30-11-2011 Enigmes Mathématiques
P2T
2 soeurs pour 49 ans par ElLapinou
07-03-2016 Enigmes Mathématiques
P2T
21-08-2009 Enigmes Mathématiques
P2T
Jeux à deux 4 par Vasimolo
01-11-2011 Enigmes Mathématiques

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