Solution au problème de decembre 2004

Le jeu des tuques (pour les mois d'hiver)

Alice et ses amis Bernard et Christian sont choisis pour jouer au "jeu des tuques": Ils seront assis en cercle de telle sorte qu'ils puissent se voir mutuellement mais ne puissent pas s'entendre. Chacun recevra un sac contenant une tuque à pompon rouge et une tuque à pompon blanc. On leur mettra un bandeau sur les yeux, puis ils sortiront une tuque du
sac et se la mettront sur la tête. Ensuite les bandeaux seront enlevés, et chacun pourra voir la couleur du pompon sur la tête des autres mais pas sur la leur. Ils ne pourront pas communiquer par signes ou en criant, et chacun devra murmurer a un arbitre à côté d'eux "je pense que mon pompon est blanc", "je pense que mon pompon est rouge" ou "je passe".
Si au moins un des trois devine correctement et aucun ne devine incorrectement, ils gagnent tous un voyage à Moose Jaw. Sinon ils gagnent seulement des jujubes.

Alice et ses amis peuvent établir une stratégie avant le début du jeu, pour se donner de meilleures chances de gagner. Par exemple, ils peuvent décider qu'Alice seule devinera, et les autres passeront. Cette stratégie leur donne une chance sur deux de gagner. Est-il possible de
faire mieux?

Solution au problème MP46

Nous aurions du préciser que les réglements ne permettent aucun signal d'aucune sorte entre les participants: ils répondent tous en même temps, et leurs réponses sont entendues seulement de l'arbitre. En fait la solution doit utiliser un raisonnement mathématique plut√t qu'une tricherie. Plusieurs de nos correspondants nous ont proposé des stratégies comportant des signaux comme ceux utilisés au bridge. Cependant nous avons reçu des réponses correctes de Xavier Hecquet (France), Wolfgang Kais (Allemagne), Patrick LoPresti (Etats Unis), Dat Phan (Regina), et Lionel Ruiz (France).

La stratégie optimale:

Cette stratégie donne 75% des chances à l'équipe de gagner. En effet, notons qu'il y a huit répartitions possibles des couleurs, toutes équiprobables:

Dans le premier et le dernier cas, touts les pompons ont la même couleur. En suivant notre stratégie, les trois participants vont deviner incorrectement. Dans tous les autres cas, un seul participant devine correctement et l'équipe gagne. Ainsi, l'équipe a six chances sur huit de gagner. Notons que chaque joueur a toujours une chance sur deux de deviner correctement la couleur de son pompon, mais notre stratégie lui donne plus de chances de passer que de deviner, et lorsqu'il passe il est sur de gagner. C'est une leçon importante -- selon Gabriel Seroussi, directeur de recherche en théorie de l'information aux laboratoires HP: "Si l'évidence suggére que quelqu'un d'autre que vous dans votre équipe en sait plus que vous, ne parlez pas.''

Lo Pesti nous démontre qu'il est impossible de faire mieux que 75% en respectant les règles et en utilisant une stratégie déterministe. Considérons une situation S où l'équipe gagne parce que le joueur X devine correctement. Alors pour la situation S' obtenue de S en changeant la couleur du pompon de X, l'information donnée à X est la même que dans la situation S, donc la réponse de X demeure la même, mais c'est alors la mauvaise réponse et l'équipe perd. Ainsi, dans toute stratégie, toute situation gagnante peut être transformée en situation perdante en changeant une seule couleur de pompon. On voit donc qu'il doit y avoir au moins deux situations perdantes.

Commentaires
On peut jouer ce jeu avec plusieurs joueurs. Le problème général est de trouver une stratégie qui maximise les chances de gains d'une équipe de n joueurs. Sous cette forme, le problème se réduit à un problème non résolu en théorie des codes correcteurs (les codes qui sont utilisés dans les transmission de données, les téléphones cellulaires, et les disques lasers) et dans les codes de recouvrement (qui sont utilisés dans la compression de données). Le problème est discuté dans le New York Times (10 avril 2001; voir

et il a aussi fait l'objet d'articles dans Scientific American et la revue "Focus'' de la Mathematical Association of America. (Désolé, nos références sont un peu floues.)