posté 01/08/20 (22:22)
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.
