Solution au problème MP34

Alexander Potapenko (Russie) et Patrick J. Lo Pesti (Etats Unis)
nous justifient une même solution à travers deux approches différentes:

Approche de Potapenko:
Si le joueur aux yeux bandés sait que la couleur des chapeaux alterne (Noir blanc noir blanc qu'on note NBNB, ou l'inverse BNBN), il lui suffit de demander aux joueurs sur les chaises 2 et 4 de changer de chapeau pour que les quatres joueurs portent des chapeaux de la même couleur. Notons 0X0X cette demande.

Si le joueur aux yeux bandés sait que deux joueurs portent un chapeau blanc et les deux autres un chapeau noir, alors il fait face à six dispositions possibles: les deux vues ci-haut NBNB, BNBN, et quatre nouvelles BBNN, BNNB, NBBN ou NNBB ou les chapeaux identiques sont adjacents. La demande 0X0X a pour effet de terminer le jeu si on fait face à une des deux premières dispositions, et de remplacer les quatre autres par une disposition similaire. (En effet, la rotation des joueurs ne change pas le fait que les chapeaux identiques sont adjacents.) Dans ce dernier cas, le joueur aux yeux bandés fait alors la demande 00XX, ce qui termine le jeu ou transforme la disposition en BNBN ou NBNB; il suffit alors de répéter la demande 0X0X pour terminer le jeu. Ainsi, la séquence

0X0X, 00XX, 0X0X

règle tous les cas où deux chapeaux sont blancs et les deux autres noirs.

En général, le joueur aux yeux bandés n'a aucune information. Il peut cependant commencer par les trois demandes 0X0X, 00XX, 0X0X, ce qui, comme on l'a vu plus auparavant, lui permet de terminer le jeu si au départ deux joueurs portent des chapeaux blancs et les autres des chapeaux noirs. Le jeu continue si au départ, il y avait trois chapeaux d'une couleur et un de l'autre; les trois demandes ci-haut n'ont fait que répéter cette situation. Le joueur aux yeux bandés peut alors faire la demande X000, ce qui termine le jeu ou transforme la disposition de telle sorte qu'il y ait maintenant deux chapeaux blancs et deux chapeaux noirs. Dans ce dernier cas, Le joueur aux yeux bandés n'a qu'à répéter les trois demandes 0X0X, 00XX, 0X0X pour terminer le jeu. Ainsi, la suite de demandes

0X0X, 00XX, 0X0X, X000, 0X0X, 00XX, 0X0X.

permet au joueur aux yeux bandés de terminer le jeu.

Potapenko démontre ensuite qu'aucune séquence de moins de sept demandes peut garantir que le jeu se termine. La démarche de Lo Pesti que nous présentons maintenant examine les demandes à partir du début plutôt que de la fin, et démontre en fait que la suite de demandes ci-haut est en fait la seule qui assure de terminer le jeu en sept demandes ou moins.

Approche de Lo Pesti:
Les configurations possibles des chapeaux se répartissent en quatre classes:

1. Tous les chapeaux sont de la même couleur, ce que nous noterons 0000
2. Trois chapeaux d'une couleur et un chapeau de l'autre couleur: 0001
3. Deux chapeaux blancs adjacents et deux chapeaux noirs adjacents: 0011
4. La couleur des chapeaux alterne: 0101.

Chacune de ces classes est préservée par les rotations des joueurs. De plus, compte tenu de ces rotations, le joueur aux yeux bandés peut se restreindre aux trois demandes 0X0X, 00XX et X000 présentées dans la solution de Potapenko. Examinons l'effet possible de ces demandes sur les configurations ``non terminales'' 0001, 0011 et 0101:

1. 0X0X transforme 0001 en 0001; 0011 en 0011; et 0101 en 0000.
2. 00XX transforme 0001 en 0001; 0011 en 0000 ou 0101; et 0101 en 0011.
3. X000 transforme 0001 en 0000, 0011 ou 0101; 0011 en 0001; et 0101 en 0001.

On peut alors examiner la suite de demande une à une, et se restreindre aux demandes efficaces à chaque étape. Les configuration initiales possibles sont 0001, 0011, 0101; ce qu'on note C₀ = {0001, 0011, 0101}. On exclue ici 0000 qui indique que tous les joueurs ont la même couleur chapeau, puisqu'alors le jeu se termine. De même, on excluera de toutes les listes de configurations, donnant seulement les configurations possibles si le jeu se poursuit. Les demandes 00XX et X000 donneraient les mêmes configurations possibles après une demande, et tout serait à recommencer. La seule demande initiale efficace est donc 0X0X, qui transforme l'ensemble des configurations possibles en

C₁ = {0001,0011}.

Ensuite, la demande 0X0X ne ferait que répéter C₁, ce qui est inutile, et la demande X000 transformerait C₁ en C₀, ce qui est pire. La seule demande efficace est donc 00XX qui transforme C₁ en

C₂ = {0001,0101}.

Ensuite, 00XX transformerait C₂ en C₁, et X000 transformerait C₂ en C₀. Seule la demande 0X0X fait progresser les choses en transformant C₂ en

C₃ = {0001}.

Maintenant, 00XX et 0X0X préserverait C₃, et seule X000 permet de la transformer en

C₄ = {0011,0101}.

Ensuite, 00XX préserve C₄ tandis que X000 le transforme en C₃, donc il faut faire la demande 0X0X pour obtenir

C₅ = {0011}.

Encore une fois, X000 transformerait C₅ en C₃, tandis que 0X0X préserverait C₅, donc seule 00XX permet de progresser, pour obtenir

C₆ = {0101}.

A ce moment, 0X0X permet de terminer la partie. On voit donc qu'il y a une seule suite de demandes qui permet de progressivement transformer l'ensemble des configurations possibles sans jamais stagner ou revenir en arrière, soit la suite

0X0X, 00XX, 0X0X, X000, 0X0X, 00XX, 0X0X.

En particulier, il n'y a pas de suite plus courte qui assure de terminer la partie.

Notes. Francesco Barioli a trouvé ce problème (en italien) sur le site
http://web.tiscali.it/no-redirect-tiscali/paololicheri/logica/l004x.htm.
Ses commentaires sont donnés sur notre page anglaise.