Draziel a écrit :Rappel :
Situation initiale : Plateau avec des pièces mises n'importe comment, et une case contient une clé.
Joueur 1 : Retourne exactement une pièce
Joueur 2 : Arrive, regarde le plateau et devine où se situe la clé.
L'indication que je donnais, c'est ce que doit faire le joueur 2 (en voyant le plateau, il fait un calcul de XOR et en déduit où se situe la clé). Ce qu'il faut montrer, c'est que cette fonction permet effectivement de gagner à tous les coups, autrement dit que quelque soit la situation intiale, le joueur 1 peut, en retournant une pièce, se débrouiller pour que joueur 2 trouve la clé. On dira qu'un plateau "désigne" la case obtenue par XOR des cases avec des pièces à pile.
Voilà un exemple pour aider à comprendre comment ça marche :
Spoiler
Les cases sont donc 00, 01, 10, 11, on peut, comme le suggère l'indication, construire le XOR des pièces à pile.
Par exemple, si le plateau est P, F, P, P, Joueur 1 calcule le XOR de 00, 10, et 11, et en déduit que le plateau "désigne" la case 01.
S'il veut que le plateau désigne 00, il retourne la case 01 (le plateau est alors PPPP, qui désigne bien 00)
S'il veut désigner la case 01 (celle qui est déjà désignée), il retourne 00.
S'il veut désigner la case 10, il retourne 11.
S'il veut désigner la case 11, il retourne 10.
Autrement dit : il retourne la case qui est le XOR entre la case actuellement désignée par le plateau et celle qu'il veut que le plateau désigne. On peut se convaincre aisément que cela fonctionne.
Reste à déterminer comment ça peut se généraliser pour d'autres valeurs que 4, puis à montrer qu'il n'y a pas de solution dans les autres cas !
![[*b]](http://img7.kraland.org/s/4F.gif)
curieux