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 :


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 !

Je n'ai clairement pas le niveau :D

Draziel a écrit :

> Je ne comprend pas comment le XOR permet de désigner une case, par exemple quand tu
> dis "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." ce que je vois c'est
> que XOR de 00=0, XOR de 10=1, XOR de 11=0...

Ah, j'ai utilisé un raccourci : quand on parle de faire du XOR de nombres à plusieurs bits, on fait généralement du XOR bit-à-bit : autrement dit un XOR de tous les premiers bits ensemble, puis un XOR de tous les deuxièmes bits ensemble.

Avec 00, 10 et 11, cela donne (0 ⊕ 1 ⊕ 1 = 0), (0 ⊕ 0 ⊕ 1 = 1) donc 01.

Le XOR-bit-à-bit entre deux nombres à plusieurs bits (que je note aussi ⊕) conserve les propriétés intéressantes du XOR, par exemple, si A et B sont deux nombres en binaire : A ⊕ B ⊕ B = A

Or justement, dans cette situation, si le plateau désigne A, tu voudrais qu'il désigne B. Il suffit alors de voir que A ⊕ (A⊕B) = B (autrement dit, en retournant la pièce (A⊕B) d'un plateau qui désigne A, le plateau va désigner B).

Merci des éclaircissements ! Effectivement je comprend beaucoup mieux comme ça !

Uncurieux a écrit :


il me semble que la méthode se généralise à tous les entiers qui sont une puissance de 2 : on numérote les case en binaire, le XOR des case avec un Pile fait un certain nombre, et on est capable de changer n'importe quel digit de ce XOR en changeant de sens la pièce de la case désignée par ces digits (plus précisément, la case qui a des 1 sur ces digit et des 0 sur les autres). Pouvant changer n'importe quelles digits, on peut désigner n'importe quelle case du plateau avec un seul changement de sens, pour toute les positions initiales.

une peu de formalisme pour ceux qui tenteraient de continuer le problème (personnellement j'abandonne) :

1/ ce que voit le second joueur, c'est un plateau dans un certain état ; il n'a pas d'autres informations (il ne sait pas l'état initial, quelle pièce a été retournée etc). A partir de cet état, il doit choisir une case. L'enjeu est donc de créer une fonction f prenant en argument un état du plateau X et renvoyant une case.

Un état du plateau est un élément de {F,P}^n (une suite de n P et F). Il contient 2^n élément.

On a n cases, qu'on peut par exemple numéroter de 0 à n-1 (pour rester raccord avec l'exemple à 4 cases, où les cases sont numérotées de 0 à 3, et leur nombre noté en binaire).

On veut donc créer une fonction f: {F,P}^n -> les entiers de 0 à n-1.


2/ évidemment ce n'est pas la seule contrainte pour f. On a, par ailleurs, n mouvements élémentaire qu'on peut noter m0, m1,... m_(n-1), m_i consistant à retourner la pièce de la case i. Pour un état donné du plateau noté X, on peut noter X+m_i l'état du plateau après avoir effectué le mouvement m_i.

Par exemple, si X = FFF, X+m2 = FPF, X+m2+m1 = PPF, X+m2+m1+m2 = PFF, etc.

L'ordre des mouvements n'importe pas (c'est pour ça que j'ai utilisé la notation "+" : X+m1+m2 = X+m2+m1). Faire deux fois le même mouvement revient à la position initiale (X+m1+m1=X).

le premier joueur voit le plateau dans un état X quelconque, et doit pouvoir désigner n'importe quelle case avec un unique mouvement. En d'autres termes, pour tout X fixé, la fonction qui a un mouvement m associe la case f(X+m) doit être surjective. Puisque par ailleurs, on a autant de mouvements que de cases, il faut que cette fonction soit bijective.

On peut noter f_X la fonction qui, à un mouvement m donné, associe f(X+m). La contrainte s'écrit alors pour pouvoir résoudre le problème :
pour toute position X, f_X définie par f_X(m) = f(X+m) est une bijection de l'ensemble des mouvements vers l'ensemble des cases.


3/ De ceci, on peut facilement établir que deux état du plateau séparés de deux mouvements désignent forcément une case différente par f. En effet, les état X+mi+mj et X sont a un mouvement de X+mi, et f_(X+mi) étant injective, f(X) = f_(X+mi)(mi) est différent de f(X+mi+mj)=f_(x+mi)(mj).


3a/ de là on déduit rapidement que le problème n'a pas de solution pour n=3. En effet, si f est une telle solution et X est un état, alors f(X+m1+m2+m3) doit être différent de f(X+m1), f(X+m2) et f(X+m3) ; mais f_x étant surjective, f(X+m1), f(X+m2) et f(X+m3) désignent les 3 cases du plateau. f(X+m1+m2+m3) ne peut donc désigner aucune case.


... Et de là je bloque. on peut montrer que le système n'a pas de solution pour n=5 et n=6 (en vrai ça ne demande pas de creuser loin dans la combinatoire), de là je conjecture qu'il n'y a de solution que si n est une puissance de 2, mais j'arrive pas à trouver de méthode qui se généralise.

Gonzo a écrit :

Wow, c'est impressionnant ! Merci d'avoir pris le temps de rédiger tes recherches !

Donc déjà, pour n puissance de 2, tu as parfaitement raison, la généralisation se fait bien.

Pour les autres cas, voici le petit truc qui te manquait, et je précise un peu le vocabulaire : on parle en fait d'un graphe : chaque sommet est un plateau, deux sommets sont reliés si on peut passer d'un à l'autre avec exactement un déplacement, et l'objectif est donc de faire en sorte que chaque sommet ait un voisin associé à n'importe quelle case du plateau.

Or un sommet a toujours exactement n voisins. Un sommet associé à 1 permet donc de couvrir exactement n sommets (il permet à n sommets d'avoir un voisin associé à 1, quoi). Il faut donc 2^n / n sommets associé à 1 pour tous les couvrir, au moins. De même, il faut 2^n / n sommets associés à 2, etc. Et le seul moyen d'avoir ça, c'est que 2^n soit divisible par n, ce qui arrive très exactement si n est une puissance de 2.

(en espérant que ce soit clair)

Uncurieux a écrit :

> (en espérant que ce soit clair)

Oui ça l'est.

Pour ceux qui préfèrent une démonstration uniquement en combinatoire, sans graphe (c'est exactement la même démo, c'est juste les outils qui changent) :

Déjà en reprenant les notations que j'ai introduite, on considère qu'il existe une fonction f résolvant le problème. On va noter E l'ensemble de toutes les positons du plateau (il a 2^n éléments), et E_i = {Y | f(Y) = i}. On va montrer que le cardinal de E_i est exactement 2^n/n (ce qui prouvera que 2^n/n est entier : un cardinal est toujours entier).

On choisit un i. pour n'importe quel Y dans E_i, {X | X est à un mouvement de Y} a pour cardinal n (on a n mouvements, qui mènent à les position différentes). Par ailleurs, la réunion suivante :
U_(Y élément de E_i) {X | X est à un mouvement de Y}
est égale à E : toute position est à un mouvement d'une position renvoyant i. Le cardinal d'un union est inférieur à la somme des cardinaux :
somme_(Y élément de E_i) card {X | X est à un mouvement de Y} >= 2^n
et somme_(Y élément de E_i) card {X | X est à un mouvement de Y} = somme_(Y élément de E_i) n = n * card E_i
L'on en ressort n * card E_i >= 2^n, soit card E_i >= 2^n/n.

Par ailleurs, U_i E_i = E, et il s'agit d'une union disjointe ; le cardinal de E est donc exactement la somme des cardinaus des E_i :
2^n = somme_(i entre 0 et n-1) card E_i >= somme_(i entre 0 et n-1) 2^n/n = n* 2^n/n = 2^n
Le seul cas d'égalité possible dans la précédente inégalité correspond au cas où chaque card E_i vaut exactement 2^n/n.

On a donc établi que 2^n/n est entier. La fin est de l’arithmétique de base : les seuls diviseurs de 2^n sont les puissance de 2.

Bien que vraiment pas fan de problèmes d'échec, en voilà un mignon :

« Blanc joue et ne gagne pas immédiatement. »



Indication :