Maths et Délires
Des maths et des délires
 

Maths et Délires Index du Forum

 FAQFAQ   RechercherRechercher   Liste des MembresListe des Membres   Groupes d'utilisateursGroupes d'utilisateurs   S'enregistrerS'enregistrer 
 ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Encore un problème de chapeaux...
Aller à la page 1, 2  Suivante
 
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Discute
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 20 Oct 2009, 8:32    Sujet du message: Encore un problème de chapeaux... Répondre en citant

Bon, j'aurais peut-être dû poster dans les fora de maths, mais comme c'est ni vraiment des maths olympiques, ni vraiment des maths supérieures, je poste dans discute Razz

C'est encore un problème de prisonniers et de chapeaux. Il y a trois prisonniers, qui ont chacun un chapeau blanc ou noir sur la tête. Ils sont disposés en rond, de sorte qu'ils voient les chapeaux des deux autres mais pas le leur. Ils doivent, exactement au même instant, dire soit "noir", soit "blanc", soit "je ne sais pas". Pour être libérés, il faut et il suffit qu'il y en ait au moins un qui annonce la couleur de son chapeau, et qu'aucun n'annonce la mauvaise couleur.
Ils peuvent discuter d'une stratégie avant qu'on leur mette les chapeaux, mais n'ont plus le droit de communiquer après. Il faut montrer qu'ils peuvent établir une stratégie qui leur permet de gagner avec probabilité 3/4 (on suppose que la distribution des chapeaux est aléatoire selon une loi uniforme Wink).


Il paraît que pour le même problème avec 7 prisonniers au lieu de 3, on peut établir une stratégie pour être libérés avec probabilité 7/8... Mais je n'ai pas trouvé laquelle...
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
Salque
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 3271
Localisation: Salle Info 3 (ou salle Infi si je suis pressé)

MessagePosté le: 20 Oct 2009, 19:58    Sujet du message: Répondre en citant

Première réaction : comme le nombre de stratégies est fini, on pourrait essayer toutes les passer en revue. Plus précisément, il y en a (après un rapide calcul) 3^12... ouais, c'est un peu chaud quand même. Pour 7, ça fait 7^(2^6*7)... là faut peut-être envisager autre chose Smile
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Overlord
Être mi-geek mi-globzoule


Inscrit le: 23 Juin 2005
Messages: 2446
Localisation: Belgique, Louvain-La-Neuve, Bâtiment des Fous.

MessagePosté le: 20 Oct 2009, 20:17    Sujet du message: Répondre en citant

Euh je pige pas très bien. Ils doivent parler en même temps, mais que peuvent-ils faire d'autre pour transmettre de l'info ?

Ils ne peuvent pas utiliser l'option "ne pas parler" pour transmettre de l'info vu qu'au moment où X doit décider s'il parle ou pas, il ne sait pas encore si les autres vont parler ou pas, et s'ils sont pas synchro, ils sont zigouillés...
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.

Il y a 11 catégories de gens sur Terre :
- Ceux qui vont sourire à cette blague parce qu'ils connaissent le binaire
- Ceux qui la connaissent et qui connaissent le binaire
- Ceux qui ne comprennent pas
Mais 10 d'entre eux ont VRAIMENT besoin de lâcher leur ordi...
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger MSN Messenger
Salque
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 3271
Localisation: Salle Info 3 (ou salle Infi si je suis pressé)

MessagePosté le: 20 Oct 2009, 21:29    Sujet du message: Répondre en citant

Si j'ai bien compris, ils ne transmettent pas d'info. La seule info qu'ils ont, ce sont les couleurs qu'ils voient. Mais bon, chacun a quand même les deux tiers de l'info, et à eux trois ils ont deux jokers... donc ça n'a pas l'air complètement désespéré !
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 20 Oct 2009, 21:35    Sujet du message: Répondre en citant

Raisonnement naïf et faux : si je vois 2 chapeaux de la même couleur, j'ai probablement un chapeau de la couleur opposée, alors que si je vois deux chapeaux de couleurs différentes, je ne sais rien sur la couleur de mon chapeau. C'est faux, certes, mais...
Stratégie : je dis "je ne sais pas" si je vois deux chapeaux de couleurs opposées, et sinon je dis la couleur opposée à la couleur des chapeaux que je vois. On vérifie que l'on gagne 3 fois sur 4 comme ça (i.e. sauf quand les 3 chapeaux sont de la même couleur, soit deux fois sur huit).
Et hop !
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 21 Oct 2009, 10:09    Sujet du message: Répondre en citant

Ouais, j'ai trouvé la même chose que toi, Antony.
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 21 Oct 2009, 22:23    Sujet du message: Répondre en citant

Et pour 7 personnes, la première remarque que j'ai faite, c'est que 7/8 est la probabilté d'avoir des chapeaux répartis 4:3 ou 5:2. Le problème, c'est que quand quelqu'un voit une répartition 4:2, il ne peut pas décider s'il est en 4:3 ou en 5:2, et donc s'il doit parler ou non. Du coup je cherche un solution en asymétrisant les rôles, pour espérer mordre un peu sur les cas 6:1 et 7:0 aussi peut-être...
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 22 Oct 2009, 10:33    Sujet du message: Répondre en citant

Ouais... Mon raisonnement a à peu près atteint le même point que le tien Wink Ce qui ne nous avance pas beaucoup Mr. Green
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
super babouin
Matheux(se) cinglé(e)


Inscrit le: 01 Juin 2006
Messages: 490
Localisation: Go back to where ye belong, ye demon from hell!

MessagePosté le: 12 Nov 2009, 20:20    Sujet du message: Répondre en citant

Indice : pensez Hamming.
_________________
Alors Renvoyer p
Sinon gnature <- vrai
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 13 Nov 2009, 16:53    Sujet du message: Répondre en citant

Tiens, je me rappelais même plus que j'avais posté ce problème...
Mais ton indication me semble logique Smile
Bon, là j'ai la flemme, je regarderai ça plus tard. (oupa)
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
super babouin
Matheux(se) cinglé(e)


Inscrit le: 01 Juin 2006
Messages: 490
Localisation: Go back to where ye belong, ye demon from hell!

MessagePosté le: 14 Nov 2009, 14:53    Sujet du message: Répondre en citant

On avait eu ça l'année dernière en DM de théorie de l'information.
_________________
Alors Renvoyer p
Sinon gnature <- vrai
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 14 Nov 2009, 20:42    Sujet du message: Répondre en citant

En fait, ce problème a été posé en introduction à un cours de théorie de l'information/codage que je suis.
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
Jill-Jênn
Au fait, on t'avait dit d'arrêter de flooder


Inscrit le: 23 Juin 2005
Messages: 6360
Localisation: ENS Cachan, France, Europe, Terre, Univers, ENS Cachan...

MessagePosté le: 17 Nov 2009, 22:28    Sujet du message: Répondre en citant

… que tu es ?
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Visiter le site web du posteur Adresse AIM Yahoo Messenger MSN Messenger
Salque
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 3271
Localisation: Salle Info 3 (ou salle Infi si je suis pressé)

MessagePosté le: 17 Nov 2009, 22:51    Sujet du message: Répondre en citant

Qu'elle suit.
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Jill-Jênn
Au fait, on t'avait dit d'arrêter de flooder


Inscrit le: 23 Juin 2005
Messages: 6360
Localisation: ENS Cachan, France, Europe, Terre, Univers, ENS Cachan...

MessagePosté le: 18 Nov 2009, 3:31    Sujet du message: Répondre en citant

Genre tu n'as pas compris que j'avais compris.
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Visiter le site web du posteur Adresse AIM Yahoo Messenger MSN Messenger
Salque
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 3271
Localisation: Salle Info 3 (ou salle Infi si je suis pressé)

MessagePosté le: 18 Nov 2009, 9:57    Sujet du message: Répondre en citant

Genre tu n'as pas compris que j'avais compris que tu avais compris.
_________________
Ceci est un virus de signature. Recopiez-le dans votre signature, s'il vous plait.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Cerise
Admin gentil


Inscrit le: 23 Juin 2005
Messages: 3323
Localisation: Rennes

MessagePosté le: 18 Nov 2009, 15:22    Sujet du message: Répondre en citant

Bon alors. Si vous connaissez le code de Hamming, ce que je vous raconte devrait être clair comme de l'eau de source. Et si vous le connaissez pas, normalement vous devriez pouvoir vérifier (plus ou moins) facilement chacune de mes affirmations.
Les prisonniers se numérotent de 1 à 7. En tout, il y a 128 configurations possibles. On considère l'ensemble C de configurations suivant :
BBBBBBB
NBBBNNB
BNNNBBN
BNBBBNN
NBNNNBB
NBNBBBN
BNBNNNB
NNBNBBB
BBNBNNN
BNNBNBB
NBBNBNN
BBNNBNB
NNBBNBN
BBBNNBN
NNNBBNB
NNNNNNN
Il y en a 16.
Pour une configuration quelconque, il existe une, et une seule configuration de C qui en diffère par au plus un élément (*).
La stratégie est la suivante : chaque prisonnier voit les 6 chapeaux des autres, et considère les deux configurations que cela donnerait, selon la couleur de son propre chapeau. Il y a deux cas possibles :
- soit l'une de ces configurations est dans C, et dans ce cas il annonce la couleur correspondant à l'autre configuration.
- soit aucune de ces configurations n'est dans C, et dans ce cas il dit qu'il ne sait pas.
D'après mon affirmation (*), il y a au moins un prisonnier qui est dans le premier cas.

Le cas défavorable aux prisonniers correspond donc exactement au cas où la configuration de chapeaux est dans C, ce qui arrive avec probabilité 1/8.
_________________
Twisted Evil Victime vengeresse Twisted Evil

amo ergo sum

Méfiez-vous de l'assassinat ; il conduit au vol et, de là, à la dissimulation.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Adresse AIM Yahoo Messenger
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 18 Nov 2009, 16:15    Sujet du message: Répondre en citant

Joli :)
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Jill-Jênn
Au fait, on t'avait dit d'arrêter de flooder


Inscrit le: 23 Juin 2005
Messages: 6360
Localisation: ENS Cachan, France, Europe, Terre, Univers, ENS Cachan...

MessagePosté le: 19 Nov 2009, 1:10    Sujet du message: Répondre en citant

Salque a écrit:
Genre tu n'as pas compris que j'avais compris que tu avais compris.
Si, en fait. Mais j'hésitais un peu.
_________________
« Être amoureux, ce n'est qu'une erreur de jugement temporaire. Un peu comme une maladie mentale. »
— Haruhi, dans La Mélancolie de Haruhi Suzumiya
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail Visiter le site web du posteur Adresse AIM Yahoo Messenger MSN Messenger
super babouin
Matheux(se) cinglé(e)


Inscrit le: 01 Juin 2006
Messages: 490
Localisation: Go back to where ye belong, ye demon from hell!

MessagePosté le: 19 Nov 2009, 2:30    Sujet du message: Répondre en citant

Salque a écrit:
Genre tu n'as pas compris que j'avais compris que tu avais compris.

http://tvtropes.org/pmwiki/pmwiki.php/Main/IKnowYouKnowIKnow
_________________
Alors Renvoyer p
Sinon gnature <- vrai
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Discute Toutes les heures sont au format GMT + 2 Heures
Aller à la page 1, 2  Suivante
Page 1 sur 2

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com