Bonsoir,
Suite à des recherches sur un sujet découvert récemment, je suis tombée sur un joli problème (du moins selon mes critères).
Il y a une équipe de n participants et l'organisateur va leur attribuer à chacun d'entre eux un chapeau noir ou blanc en tirant à pile ou face. Les participants peuvent voir tous les chapeaux des autres mais pas le leur. Ils ne peuvent pas communiquer entre eux pendant l'expérience et ne peuvent pas entendre la réponse des autres participants.
Chacun d'entre eux va répondre "noir" ou "blanc" ou "abstention". L'équipe gagne si au moins un participant a donné la couleur de son propre chapeau et qu'aucun d'entre eux n'a donné la couleur qui n'est pas celle de son propre chapeau.
Ils se sont mis d'accord avant l'expérience, quelle est la meilleure stratégie et la probabilité de gagner pour différentes valeurs de n ? Je conseille vivement de commencer par les petites de valeurs de n qui vous inspirent et d'ailleurs je ne suis pas sure de ma réponse pour toutes les valeurs de n.
Bonjour,
J'ai quelques doutes sur mon approche, notamment parce qu'elle manque de rigueur, mais sait-on jamais
Bonjour ,
Non, non, il s'agit bien d'une pièce parfaitement équilibrée. C'est une suite de variables iid selon une loi qui va donner blanc avec une proba 1/2 et noir avec une proba 1/2 comme il se doit. Pas de piège dans l'énoncé, ni coup tordu mais une stratégie à trouver pas du tout évidente, c'est l'intérêt. Essaye pour n=3 peut-être pour commencer.
Stratégie bêbête : tout le monde s'abstient sauf un qui répond au hasard blanc ou noir. Ça fait bien sûr une chance sur deux de gagner.
Il s'agit de faire mieux.
carpediem, l'ordre n'a pas d'importance, ils pourraient répondre tous en même temps que ça ne changerait rien à l'histoire puisqu'ils ne connaissent pas les réponses des autres. Mais il y a de l'idée dans le fait de tout miser sur un seul et même individu. Le problème c'est que si on choisit cet individu à l'avance par exemple le dernier d'une numérotation sans lien avec la couleur des chapeaux, on aura la stratégie de GBZM. C'est pas mal mais c'est clair que j'attends mieux à partir de n=3 sinon je ne vous aurai pas dérangé pour si peu.
Bonjour,
"ni coup tordu" tu disais ? J'ai une stratégie pour n=3, mais c'est plutôt tordu, donc je doute un peu.
Le cas général me demanderait beaucoup trop de réflexion et je préfère ne pas me lancer dedans.
Je présente quand même la manière dont j'aurais abordé une généralisation :
On numérote les joueurs de à .
On définit les fonctions
indique ce que dira le joueur en fonction des chapeaux qu'il voit.
Pour chaque tirage, on a , et on peut vérifier si on gagne ou si on perd.
En sommant, on obtient la probabilité de victoire.
Pour , on note le vecteur dont on a retiré la -ème coordonnée.
Le joueur dit alors où est la liste des couleurs des chapeaux.
Une idée serait de remarquer les cas où un joueur a raison, et de forcer tous les autres à dire .
C'est-à-dire :
pour tout , s'il existe tel que .
Alors pour tout
A chaque fois qu'on choisit une image d'un différente de , beaucoup d'autres sont fixées, et des hypothèses de ce genre permettent de limiter les possibilités.
Mais on démarre quand même avec possibilités pour définir tous les .
Pour , c'est , mais on a des symétries permettant de réduire les calculs.
Dans le cas général, en expliciter suffisamment me paraît très compliqué.
Je reviens sur la configuration avec 3 joueurs.
J'ai douté un certain temps, je me disais qu'il y avait une histoire de proba conditionnelle, mais non. Ca colle.
On peut recenser les 8 configurations possibles.
Il y a 6 cas où l'équipe va gagner. Et sur ces 6 cas, on aura 6x1=6 bonnes réponses.
Et il y a 2 cas où l'équipe va perdre. Et sur ces 2 cas, on aura 2x3=6 mauvaises réponses.
Au final, on a bien le même nombre de bonnes réponses et de mauvaises réponses.
Ouf.
Si on avait 2 valeurs différentes, il faudrait chercher l'erreur quelque part.
Bien vu ty59847,
C'est exactement ce phénomène qu'on essaye de produire !
Regrouper les mauvaises réponses sur le moins de cas possibles pour que tout le monde se trompe et répartir les bonnes réponses sur le plus de cas possible pour qu'un seul individu nous sauve la mise.
On ne pourra donc pas obtenir de stratégie parfaite pour tout n d'où le fait que je conseillais de regarder les valeurs de n qui vous inspirent, quelle sera la prochaine ?
Bonjour,
Pour 3 participants
Pour n=4 joueurs, si on reproduit la même stratégie :
* il y a 16 configurations.
* Un joueur ne répond, que si les chapeaux des 3 autres joueurs sont de la même couleur.
Quand les 4 chapeaux sont de la même couleur, les 4 joueurs répondent et se trompent tous les 4. 4*2=8 mauvaises réponses.
Quand il y a 3 chapeaux d'une couleur, et un chapeau de l'autre couleur, un seul répond, et c'est une bonne réponse. 8 cas, avec une seule bonne réponse
Et dans les autres cas, les 4 joueurs s'abstiennent, donc l'équipe perd.
Au final on a bien 8 bonnes réponses et 8 mauvaises ( mon équilibre), mais on n'a que 8 cas où l'équipe gagne. Trop de cas où tout le monde s'abstient.
Le résultat est de 8/16,c'est à dire strictement la même probabilité de gagner qu'avec la stratégie basique : Un seul répond, au hasard.
On peut envisager de compléter la stratégie. Un des joueurs répondrait systématiquement. Ca permettrait d'avoir moins de défaites par abstention. Mais ça n'améliorerait pas la probabilité finale.
Pour n=5, il y a une stratégie qui gagne dans 20 cas sur 32.
Si n=5, les couleurs peuvent être réparties 5+0 (2cas), 4+1 (10 cas) ou 3+2 (20 cas).
Les joueurs vont dire : on fait ce qu'il faut pour gagner si la répartition est 3+2
Par exemple, si la répartition est BBNNN
Les 2 joueurs qui ont un chapeau Blanc ne savent pas si la répartition est BBNNN ou BNNNN, mais ils parient sur BBNNN.
Et les 3 joueurs dont le chapeau est noir voient BBNN, ils savent que la répartition est BBNNN ou NNBBB , ils ne parient pas.
A chaque fois que la répartition est 3+2, il y a 2 joueurs qui parient, et qui parient forcément sur la bonne couleur.
On a 20 cas comme ça , ça donne 20 victoires et 20x2 bonnes réponses.
A chaque fois que la répartition est 4+1, il y a 4 joueurs qui parient, et qui se trompent.
On a 10 cas comme ça, ça donne 10 victoires et 10*4 bonnes réponses.
A chaque fois que la répartition est 5+0, aucun joueur ne parie.
20x2=10x4=40 ... on a bien mon équilibre.
Et on gagne 20 fois sur 32.
Pour n=7 joueurs, on va appliquer la même stratégie. On fait le pari qu'il y a 4 chapeaux d'une couleur et 3 d'une autre.
Seuls les joueurs qui voient 4+2 parient, en espérant que la répartition est 4+3.
On gagne à chaque fois que la répartition est 4+3, c'est à dire 70 fois sur 128.
On peut même améliorer la stratégie.
On fait en sorte de gagner uniquement si la répartition est 4+3, ou 6+1.
Donc les joueurs qui s'expriment sont ceux qui voient (4+2) ou (6+0)
Si je compte bien, on gagne 84 fois sur 128.
Et on peut généraliser pour tout nombre n impair.
Par exemple pour n=15, on parie que ce sera 7+8 ou 5+10 ou 3+12 ou 1+14, et ceux qui parient sont ceux qui voient 6+8 ou 4+10 ou 2+12 ou 0+14. Ils parient systématiquement sur la couleur qui est en 'déficit'.
On gagne dès que c'est 7+8 ou 5+10 ou 3+12 ou 1+14
A priori, le résultat obtenu ainsi est toujours supérieur à 50%. Je suis très confiant, même si je n'ai pas fait le calcul.
Pour n pair, pour l'instant je n'ai rien de mieux que la stratégie basique : un seul joueur parie , et on gagne dans 50% des cas.
Bonjour, ne vous vexez pas mais je ne suis pas vraiment convaincue,
Pour la stratégie de dpi
1N 2B 3B et 1 dit B donc l'équipe a perdu et ça s'arrête là
Tu vas faire moins bien que 1/2
Pour la stratégie de ty59847
Je ne veux pas te décourager car il y a un bel effort mais l'objectif est quand même d'avoir une proba croissante (pas forcément strictement) en fonction de n.
Pour n>3, dans ma phase de préparation, je peux sélectionner 3 individus qui font la stratégie pour n=3 et les autres s'abstiennent quoi qu'il arrive. Donc on aura forcément une probabilité de victoire supérieure ou égale à celle pour n=3.
Si tu fais moins bien, bof, disons que c'est sympa de ta part d'avoir voulu faire participer tout le monde.
Snifff,
j'étais très fier de ma réponse, alors qu'il y a effectivement mieux et plus simple.
Donc, on a une stratégie qui gagne dans 75% des cas, pour n'importe quelle valeur de n>2, et la question est : y-a-t-il mieux ?
Je me doute, désolée...
Comme le prochain palier va être difficile à trouver, sachez que je me suis intéressée à ce sujet suite à une réponse de GBZM sur la distance de Hamming.
Bonjour.
Pour (et donc pour ), j'ai trouvé une stratégie qui permet d'obtenir une probabilité de gain de .
Je la décrirai prochainement (d'ici 24 heures).
Bonjour perroquet,
Joli, je sais faire aussi pas avant donc j'attends avec impatience mais prends ton temps quand même
Comme je disais au début, je ne suis pas sure de moi pour toutes les valeurs, perso j'utilise les codes de Hamming donc quand je ne suis pas de la forme je suis bien embêtée.
Bonjour.
Je me suis trompé.
La stratégie à laquelle je pensais ne permet d'obtenir qu'une probabilité de . Ce n'est donc pas intéressant.
on dira donc que perroquet est un oiseau de mauvais augure !!
néanmoins n'ayant aucune idée de comment faire à mon humble niveau je suis preneur de cette stratégie à 11/16 bien supérieur à la stratégie à 1/2 puisque proche de 3/4 ... (ou du moins les grandes lignes si c'est un peu long)
et je t'en remercierai par avance et par après ...
voila je t'en remercie par avance !!!
Notons la probabilité maximale de gain pour une équipe de participants.
Je vais montrer que la limite de quand tend vers l'infini est égale à 1.
Tout d'abord, la suite est croissante: en effet, si est supérieur à , il suffit de reprendre la stratégie pour les premiers participants sans faire intervenir les restants, et on obtiendra une probabilité de gain égale à . Ceci permet de conclure que .
De plus, la suite est majorée par 1. Elle converge donc vers une limite .
Soit et deux entiers, avec et . On cherche une inégalité reliant et . On considère la stratégie suivante pour participants:
- on sépare les participants en deux groupes de et
- les premiers suivent la stratégie qui permet d'assurer le gain maximal pour participants sauf lorsque les éléments du deuxième groupe ont au moins chapeaux de la même couleur (dans ce cas-là, ils s'abstiennent)
- chaque élément du deuxième groupe s'abstient sauf lorsque les autres éléments ont un chapeau de la même couleur; dans ce cas, il choisit la couleur opposée
La probabilité de gain avec cette stratégie vaut:
On en déduit que
En faisant tendre vers l'infini:
Et donc
Et donc
Il y a quelque chose qui me chiffonne dans ta démo @perroquet
Ne faudrait-il pas y avoir des "strictement plus grand" au lieu des "plus grand ou égal"?
En effet p(n) = 0.5 pour tout n. ne converge pas vers 1 et pourtant p(k) p(n) pour k > n et p(n) 1.
On divise l'équipe en groupe de 3 participants. Les participants qui ne sont pas dans un groupe s'abstiennent.
On ordonne ces groupes.
Tous les participants s'abstiennent sauf si les deux autres participants de leur groupe on la même couleur et que chaque groupe après eux est d'une seule couleur.
La seule façon de perdre est si chaque groupe est d'une seule couleur.
Pour n=3k+r participants, il y a (2/8)^k chance de perdre et donc rapidement beaucoup de chance de gagner.
Bonjour,
Je ne suis pas tout à fait d'accord avec le calcul de probabilités de LittleFox qui me parait un peu optimiste. On risque aussi de perdre car tout le monde se sera abstenu.
Le cas que tu décris "chaque groupe après eux est d'une seule couleur" ne se présentant jamais.
A moins que tu fasses parler le dernier groupe sous certaines conditions mais alors il y a forcément des cas où il va parler alors qu'il aurait mieux fait de s'abstenir car la victoire était déjà acquise et ils vont la faire perdre.
Peut-être qu'il y a moyen de faire quelque chose d'efficace, à voir.
perroquet a raison sur la limite qui vaut 1 et on peut même démontrer que si alors on peut créer une stratégie avec une probabilité de gagner qui vaut . A mon sens, elle est parfaite puisqu'elle va vérifier la propriété qui avait été identifiée avant. Je vous laisse essayer !
Par contre entre 2 paliers, je ne sais toujours pas quoi faire des individus en trop donc dans le doute, je leur dis de s'abstenir alors qu'il y a peut-être moyen d'optimiser
Exactement, GBZM lit bien dans mes pensées
Ce n'est pas trop difficile à généraliser, si il existe un code de Hamming
Je ne sais si tout le monde va être convaincu de pourquoi on trouve la proba annoncée, peut-être qu'il va falloir l'expliquer ?
Disons que c'est un peu du détournement d'outils sérieux pour s'amuser
Je trouve ça super joli de réussir à avoir une proba de victoire qui tend vers 1 alors que si tout le monde répond au hasard, la proba tend vers 0 et que la stratégie intuitive basique donne 1/2.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :