On numérote les cases entre 0 et 63 : étant donnée une disposition des pierres sur l'échiquier, on lui associe un nombre entre 0 et 63 en faisant la nim-addition des cases sur lesquelles il y a une pierre. Du fait des propriétés de la nim-addition sur un ensemble du type [latex][0;2^n-1][/latex], Alice peut laisser à Bob une disposition associée au nombre qu'elle veut entre 0 et 63.

Elle aurait même pu le faire si le diable lui avait imposé de modifier une case.

Celui là, si on ne l'a pas vu déja au moins une fois sous une forme ou une autre, on peut difficilement le deviner.....

On attribue à chaque case un code à 6 chiffres binaires (2^6 = 64) et on pose cette règle: code actif si pierre, code 000000 si pas de pierre.


Avec une configuration donnée, on calcule un code-somme de 6 bits: chaque bit représente la parité du nombre de bits à 1 de même rang pour toutes les cases.

La case mystère est ce code-somme.

Pour le corriger, il suffit de changer une case (ôter ou ajouter une pierre) qui représente la différence binaire du code-somme lu et du code-somme de la case mystère.
Exemple :
code-somme lu :....... 001010
code case mystère.....000111
Différence : ..............001101

On ajoute ou on ôte une pierre à la case affectée au code 001101 (case 13) pour changer la parité des bits de rang 3, 4 et 6.

On commence par se mettre d'accord pour numéroter les cases en octal. Les numéros de colonne de 0 à 7 représentent les unités, le lignes de 0 à 7 les « huitaines ».
Alice fait la somme de toutes les cases occupées par une pierre. Si cette somme modulo 64 (en décimal, soit 80 en octal) est égale au numéro de la case mystère, elle ne change rien.
Si elle est différente elle peut soit ajouter une pierre dans la case (si celle-ci est libre !) qui donnera un total modulo 64 égal au numéro de la case mystère, soit enlever une pierre dans une case (si celle-ci est remplie !) pour obtenir le même résultat.

Statistiquement, si les cases du diable sont choisies au hasard, je pense qu'Alice et Bob ont de bonnes chances de s'en tirer (je laisse aux matheux de service, le soin de calculer cette probabilité dans le cas général de N pierres ).
Mais si le diable veut vraiment être diabolique, il choisira une case mystère et un placement des pièces tels qu'aucune de ces deux conditions ne soit valide.

Un grand merci pour cette énigme qui m'est apparue au premier ras bord comme insoluble, mais qui m'a permis de bien titiller mes neurones.

Ahemm, j'espère vraiment que je ne me suis pas totalement planté haha :

Selon moi, le principe de départ sur lequel Alice et Bob devraient fonder tout leur système est le suivant : puisque le diable leur demande de trouver une stratégie sûre, c'est qu'elle doit exister. Or il apparaît tout un ensemble de conditions dans lesquelles une stratégie garantie gagnante n'est pas envisageable :
Si on imagine qu'il y a trois pierres qui sont disposées sur l'échiquier et que la case mystère est recouverte par l'une d'entre elles, on peut "difficilement" s'en sortir avec une astuce : si alors Alice tente de retirer la pierre de la case mystère, il en restera deux et il sera impossible pour Bob de savoir si la case mystère se trouve sur l'une de ces deux pierres ou sur une quelconque autre case. Il en va de même pour n'importe quel nombre plus grand de pierres qui seraient réparties de manière aléatoire. Alice et Bob auraient beau essayer, jamais ils ne trouveraient de stratégie dans de telles conditions.
Partant de ce constat, et repensant à la requête du diable de trouver une stratégie sûre, et posant l'existence d'une telle stratégie, ils conviendront que le diable aura disposé les pierres et choisi la case mystère de manière à ce qu'ils puissent infailliblement trouver la solution. Alors, ils se mettront à examiner les conditions dans lesquelles une stratégie permettrait de faire deviner la bonne case à tous les coups :

Premier cas : s'il n'y a pas de pierre sur l'échiquier, alors il faudra qu'Alice dépose une pierre sur la case mystère. Conclusion : si Bob ne trouve qu'une seule pierre sur l'échiquier, c'est que là se trouve la case mystère.
Second cas : Il y a une pierre sur l'échiquier. Si elle se trouve sur la case mystère, ne toucher à rien. Si elle se trouve autre part, il n'existe aucun moyen d'indiquer la bonne case. Alors elle ne se trouvera pas autre part. Conclusion : une fois encore, s'il n'y a qu'une seule pierre sur l'échiquier, c'est la bonne case.
Troisième cas : Il y a plus d'une pierre sur l'échiquier. La case mystère se trouve ou non sous l'une de ces pierres. Alice et Bob savent déjà que l'arrangement des pierres ne peut être chaotique. S'il y a plus d'une pierre sur l'échiquier, alors celles-ci doivent être "ordonnées" d'une manière ou d'une autre ; et alors, le seul élément de désordre qui apparaîtra dans la configuration des pierres contiendra la solution du problème. Mais quel peut être l'ordonnancement des pierres ?
Cas simple des lignes : Alice et Bob se disent que si les pierres forment des lignes simples, horizontales, verticales ou diagonales, et que la case mystère se trouve "loin" ailleurs, il suffira de poser une pierre dessus et la case se distinguera alors, son isolation exprimant sa présence. A présent qu'ils ont étudié le cas où la case mystère se trouve isolée d'une série de cases et de pierres ordonnées en lignes simples, Alice et Bob s'intéressent au cas où la case mystère se trouverait sur l'une de ces pierres. Ils pourraient penser à "retirer" la pierre de la case, et l'espace laissé entre deux lignes indiquerait la présence de la case mystère. Ainsi, Alice et Bob essaieraient de s'entendre sur une stratégie d'isolation de la case mystère, et cette isolation pourrait se manifester de deux manières : soit une pierre qui n'est pas en contact avec les autres, soit un trou qui suggère sans ambiguïté de par sa présence celle de la case mystère.

Leur système d'isolation de case dans le cas de lignes se traduit alors ainsi :

Est considérée comme isolée une case qui n'a strictement aucun contact avec une ligne de cases sur laquelle s'étend une ligne de pierres.
Une case isolée est une case remarquable, de par sa manifestation évidente sous forme d'une pierre isolée des autres pierres ou d'une case d'espace vide isolée des autres espaces vides.
Si une case est remarquable, alors il s'agit de la case mystère.

Arrivés là, Alice et Bob ont achevé le plus gros de leur travail. Mais leur vision s'étend tout à coup : et si des lignes de cases, ils élargissaient leur théorie au cas des surfaces, ou "blocs" de cases ? Ils supposent un bloc de cases rempli de pierres, puis très vite généralisent aux cas de plusieurs blocs de cases remplies de pierres occupant plusieurs surfaces de l'échiquier. Si la case mystère est isolée de tous les blocs, alors il suffira de déposer une pierre dessus. Si elle se trouve à l'intérieur d'un des blocs et qu'il est possible d'isoler cette case en retirant une pierre de manière à marquer sa présence par un trou, et à condition que ni ce bloc ni aucun autre bloc ne soit doté de trous, alors ce seul trou représentera la case mystère. Evidemment, si l'ensemble de l'échiquier est plein, il suffira de retirer la bonne pierre, et s'il n'y a qu'une seule case libre sur tout l'échiquier, alors ce sera forcément celle de la case mystère et il ne faudra toucher à rien.

Et enfin, alors qu'ils ont presque terminé, Alice et Bob s'arrêtent encore à une dernière éventualité, celle où les choses s'arrangeraient d'une telle façon que Bob se retrouverait face à un échiquier composé d'un bloc avec un trou et d'une pierre isolée. En effet, Alice et Bob s'imaginent que le diable serait capable de leur jouer un pareil coup : il lui suffirait, par exemple, de créer un carré de pierres de neuf cases, puis de retirer la pierre centrale de manière à laisser un trou à sa place, et enfinyy de choisir comme case mystère n'importe quelle case éloignée du bloc. Alice serait alors forcée de déposer une pierre sur cette case, sans pouvoir effacer le trou au milieu du bloc. Mais ils trouvent rapidement une astuce : la pierre isolée l'emportera sur le trou.

Alors, Alice et Bob résument leur stratégie collective en un unique principe :

Pour trouver la solution au problème, il faut isoler une case.

Et s'assurent de la complétude d'un tel système en le recouvrant d'un unique axiome :
S'il existe une solution au problème, alors il existe une case isolée.

Et ils résument leurs stratégies individuelles ainsi :

Pour Alice, isoler la case mystère, soit en ajoutant une pierre et en créant une pierre isolée, soit en retirant une pierre et en créant un vide isolé, un trou ; soit encore en laissant l'échiquier intact si la case mystère apparaît déjà isolément.

Pour Bob : repérer la case qu'Alice a isolée par la pierre ou par le trou, en se rassurant par le fait que si Alice n'a touché à rien, alors il devra quand même exister une case isolée.

Et s'ils n'y arrivent pas, alors c'est que les dés sont pipés et que le diable ne voulait pas qu'ils réussissent (ou que je suis con ^^).


EDIT : ah bah non, je me suis planté. J'ai pensé à faire le même raisonnement mais en partant à l'envers, en accordant la primauté au trou sur la case pleine, en allant ainsi : Si toutes les cases sont pleines alors vider la case mystère ; s'il y a un trou alors ne pas toucher à l'échiquier, et s'il y a plusieurs trous ordonnés en lignes et ou en blocs, remplir la ligne ou le bloc par une pierre si la case mystère s'y trouve, et vider la case mystère si elle se trouve sur une case pleine. Et alors dans le cas où on trouverait un trou et une case pleine, ce serait le trou qui aurait la primauté et donc c'est là que se trouverait la case mystère, non ? Alors du coup je ne comprends plus rien.
Comment interpréter le cas d'un échiquier rempli de pierres sauf dans un carré de huit cases vides et d'une case pleine (disons au centre), et où la case mystère se trouverait sur une case pleine quelconque en dehors dudit carré ? Alors si la primauté revient à la case pleine, Alice ne peut pas retirer la pierre de la case mystère car elle deviendrait un trou ; et si la primauté est accordée au trou sur la case pleine, alors un échiquier vide sauf dans un carré de huit cases pleines et une case vide (toujours la centrale), où la case mystère serait une case vide quelconque en dehors dudit carré, la case mystère serait marquée par une case pleine et non un trou.

Que faire ? Comparer la surface pleine et la surface vide de l'échiquier, et accorder la primauté à la case pleine s'il la surface pleine supérieure à la surface vide ; et accorder la primauté au trou si la surface vide est inférieure à la surface pleine ? Je ne sais pas pourquoi je propose ça...

Et puis il y a le cas d'un échiquier équitablement proportionné en surfaces vide et pleine : imaginons un échiquier rempli de pierres sur toute la surface gauche et vide sur tout la surface droite. Si la case mystère se trouve sur la surface vide, alors il suffirait d'y déposer une pierre, et si elle se trouve sur la surface pleine, il suffirait d'y retirer une pierre. Sauf qu'il semble exister deux cas impossibles à résoudre :
Une moitié de surface pleine sauf sur une case, avec la case mystère se trouvant sur une case de la surface vide. Alors il faudrait déposer une pierre dessus et accorder à la pierre la primauté sur le trou.
Une moitié de surface vide sauf sur une case, avec la case mystère se trouvant sur une case de la surface pleine. Alors il faudrait retirer la pierre dessus et accorder au trou la primauté sur la pierre.

En gros, si on a un échiquier avec une moitié de surface pleine creusée par un trou et une surface vide remplie par une pierre, on ne saura jamais où se trouve la case mystère : sur le trou entouré de pierres ou sous la pierre entourée de trous, parce qu'on saura pas si c'est le trou ou la pierre qui l'emporte.

J'avoue que je suis perdu ^^

(et je n'ai pas envie de supposer que nos deux amis seront assurés de ne pas tomber non plus sur ce cas sous prétexte que c'est encore impossible à résoudre. A l'aide...)

Bonjour

Bravo à @zobizob pour cette super énigme.
A mon grand regret je n'ai pas su la résoudre.

Continuons à faire vivre ce site !!!

Pour la suite de l'énigme :

http://www.prise2tete.fr/forum/viewtopic.php?id=13521