Un problème issu du mastermind

Olympiades mathématiques, énigmes et défis
busard_des_roseaux
Membre Complexe
Messages: 3151
Enregistré le: 24 Sep 2007, 14:50

Un problème issu du mastermind

par busard_des_roseaux » 01 Sep 2008, 18:30

Bjr,

il y a un client qui m'a appelé pour le problème suivant:


c'est un problème de mastermind posé en concours d'entrée en école d'infirmière:

il y a une solution de mastermind inconnue, exemple le triplet (1,3,5).


on présente la matrice "logique" , accompagnée des réponses
156 un chiffre à la bonne place,un chiffre à la mauvaise place
234 un chiffre à la bonne place
691 un chiffre à la mauvaise place


la question est:

déterminer un algorithme qui donne la solution (en trois coups donc)
ou des heuristiques qui donnent la réponse dans des cas particuliers.


merçi d'avance.



Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 12:07

par Doraki » 01 Sep 2008, 18:42

Il n'y a pas de stratégie pour toujours déterminer en 3 coups ne serait-ce que l'ensemble des chiffres présents dans la solution.
=/
Quant à une heuristique qui donne la réponse dans des cas particulier, je suis pas sur de comprendre ce qu'ils veulent.

Imod
Habitué(e)
Messages: 6476
Enregistré le: 12 Sep 2006, 12:00

par Imod » 01 Sep 2008, 18:45

Curieux ce 9 ! Les chiffres à deviner figurent parmi 1;2;3;4;5;6;7;8;9 ? Tolère-t-on les doublons du style 1123 ?

Imod

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 01 Sep 2008, 18:51

Obtenir la solution en 3 coups, à coup sûr ! ...c'est impossible.
123 : aucun chiffre
456 : aucun chiffre
et maintenant, il reste plusieurs (dizaines de) possibilités.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 01 Sep 2008, 18:52

Imod a écrit:Curieux ce 9 ! Les chiffres à deviner figurent parmi 1;2;3;4;5;6;7;8;9 ? Tolère-t-on les doublons du style 1123 ?
Imod

en plus tu triches... non pas à cause du doublon, mais parce que toi, tu veux cacher 4 chiffres ! :ptdr:

Imod
Habitué(e)
Messages: 6476
Enregistré le: 12 Sep 2006, 12:00

par Imod » 01 Sep 2008, 19:03

Un simple décompte montre que c'est impossible :

Nombre de possibilités à 3 chiffres :
Nombre de triplets pour le codage des 3 essais :

Ca ne colle pas !

Imod

busard_des_roseaux
Membre Complexe
Messages: 3151
Enregistré le: 24 Sep 2007, 14:50

par busard_des_roseaux » 01 Sep 2008, 21:21

je précise si ce qui est demandé à l'examen:

1) le motif caché est un arrangement de 3 parmi 10.

2) ils proposent des exercices choisis pour avoir une solution et une seule.

3) les candidats doivent apprendre des heuristiques (c'est à dire des méthodes de résolution) qui marchent dans certains cas particuliers.

La question est:

pourriez vous m'en trouver ? (des heuristiques)

je vais essayer de transformer ces "booléens" en entiers naturels.
pour l'instant, c juste une vague idée, ou plutôt en calculs dans Z/2Z

merçi d'avance.

Imod
Habitué(e)
Messages: 6476
Enregistré le: 12 Sep 2006, 12:00

par Imod » 02 Sep 2008, 00:26

Les valeurs que j'ai fournies ne correspondent pas à grand-chose mais si j'ai bien compris les nouvelles données , le problème n'est pas là . Il s'agit plus de résoudre un exercice façon problème d'échec ou de bridge : la solution est unique , comment l'obtenir ? Il me semble qu'on attend pas un algorithme mais plutôt une bonne logique .

Imod

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 02 Sep 2008, 00:37

une bonne logique ? ben, proposer des triplets aléatoires mais conformes aux réponses précédentes ...

Imod
Habitué(e)
Messages: 6476
Enregistré le: 12 Sep 2006, 12:00

par Imod » 02 Sep 2008, 00:39

Pour avoir travaillé sur le problème il y a quelques années je peux t'affirmer que ce n'est pas la meilleure stratégie .

Imod

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 00:53

par Patastronch » 02 Sep 2008, 00:45

Une bonne maximisation de l'espérance ca devrait faire une heuristique pas trop mal :)
Quand on propose une combinaison on peut mettre une loi de proba sur les indications qu'on va recevoir (bonne place ou pas, l'indication gagnante étant 3 a la bonne places), ainsi après des indication on va refaire une combinaison qui va nous donner une nouvelle distribution de probabilité et ainsi de suite jusqu'à qu'on trouve la bonne combinaison . Ainsi on peut évaluer la puissance d'un coup par son espérance de gains (cad proba de gagner en 1 coup * M-1 + proba de gagner en 2 coups * M-2 + ... ou M est le nombre de coup maximale pour gagner dans le pire cas, cette espérance renvoie donc le nombre M-a où a est la moyenne du nombre de coups nécessaire pour trouver la solution,, donc plus a est petit plus on a de chances de trouver vite) et il suffit alors de faire la combinaison maximisant cette espérance future à chaque fois qu'on doit proposer une combinaison.

P.S: En gros je propose d'appliquer l'éspérance d'utilité célèbre chez les économistes où la fonction d'utilité serait u(x)=M-x pour ce cas

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 02 Sep 2008, 00:56

Imod a écrit:Pour avoir travaillé sur le problème il y a quelques années je peux t'affirmer que ce n'est pas la meilleure stratégie .
Imod

En tout cas, elle est simple à programmer, rapide, pas "anticipable",
et vu le faible taux de réussite auquel on s'attend quelle que soit la stratégie adoptée sur 3 coups, je ne suis pas certain qu'on voit une différence nette avec une stratégie basée sur des calculs probabilistes.

Il faudrait pour cela réaliser des milliers de parties pour comparer les scores de différentes stratégies... Moi, je veux bien m'occuper de celle que j'ai donnée !

Patastronch a écrit:P.S: En gros je propose d'appliquer l'éspérance d'utilité célèbre chez les économistes où la fonction d'utilité serait u(x)=M-x pour ce cas

Es-tu partant pour la programmer ?

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 02 Sep 2008, 00:56

Patastronch a écrit:P.S: En gros je propose d'appliquer l'éspérance d'utilité célèbre chez les économistes où la fonction d'utilité serait u(x)=M-x pour ce cas

Es-tu partant pour la programmer ?

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 02 Sep 2008, 00:58

busard_des_roseaux a écrit:1) le motif caché est un arrangement de 3 parmi 10.

Donc pas de doublon dans le secret, ok.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 00:53

par Patastronch » 02 Sep 2008, 00:59

leon1789 a écrit:En tout cas, elle est simple à programmer, rapide, pas "anticipable",
et vu le faible taux de réussite auquel on s'attend quelle que soit la stratégie adoptée sur 3 coups, je ne suis pas certain qu'on voit une différence nette avec une stratégie basée sur des calculs probabilistes.

Il faudrait pour cela réaliser des milliers de parties pour comparer les scores de différentes stratégies... Moi, je veux bien m'occuper de celle que j'ai donnée !


Es-tu partant pour la programmer ?

Oui c'est justement une partie de ma thèse de travailler sur l'espérance d'utilité et j'étais en train de me dire que le mastermind était une bonne application ! :)

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 02 Sep 2008, 01:01

Patastronch a écrit:Oui c'est justement une partie de ma thèse de travailler sur l'espérance d'utilité et j'étais en train de me dire que le mastermind était une bonne application ! :)

le mastermind classique, celui où on sait qu'on va finir par trouver, ok,
mais là ?

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 00:53

par Patastronch » 02 Sep 2008, 01:03

leon1789 a écrit:le mastermind classique, celui où on sait qu'on va finir par trouver, ok,
mais là ?

Le but d'une heuristique est de guider le choix attention, on est tous d'accord qu'en 3 coups c 'est pas possible mais l'énoncé demande de proposer une bonne heuristique le cas échéant si je ne m'abuse, et donc de maximiser la probabilité de gagner. Si on veut juste maximiser la proba de gagner en 3 coups il suffit de prendre M=3 et non au max du nombre de coups nécessaire pour gagner.

Apres on peut extraire de cette heuristique des cas particuliers favorable (donc des indications particuliere au 1er et 2 eme coup) qui permetrait de gagner à coup sur.

Imod
Habitué(e)
Messages: 6476
Enregistré le: 12 Sep 2006, 12:00

par Imod » 02 Sep 2008, 01:06

leon1789 a écrit:En tout cas, elle est simple à programmer, rapide, pas "anticipable",et vu le faible taux de réussite auquel on s'attend quelle que soit la stratégie adoptée sur 3 coups, je ne suis pas certain qu'on voit une différence nette avec une stratégie basée sur des calculs probabilistes.

Le programme que tu proposes je l'ai fait il y a 30 ans quand je hantais les couloirs de la fac de sciences de Tours , j'avais poussé l'exploit jusqu'à le faire fonctionner sur ma calculatrice ( à l'époque on comptait en octets ) . Un "robot" qui propose une solution "au pif" ce n'est pas ce que j'appelle
une stratégie :--:

Imod

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 02 Sep 2008, 01:06

Ca m'intéresse tout ça.
Je vais programmer la stratégie naïve que je présente pour voir son taux de réussite. On pourra comparer.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 16:25

par leon1789 » 02 Sep 2008, 01:10

Imod a écrit: Un "robot" qui propose une solution "au pif" ce n'est pas ce que j'appelle une stratégie :--:

Ben, une stratégie non gagnante et 100% prévisible n'est pas non plus une très bonne stratégie... Je pense que la stratégie probabiliste a un énorme trou ! Si vous n'utilisez pas le hasard quelque part, alors il y a aura plein des combinaisons que cette stratégie ne trouvera jamais en 3 coups.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite