View Single Post

elyyn's Avatar


elyyn
11.23.2012 , 09:21 AM | #20
Vous vous prenez bien la tête... Le problème se ramène à un système d'équations linéaires sur F2 qui est un corps commutatif, donc on peut le traiter matriciellement, sous la forme A.X=B avec A une matrice 9x9 sur F2, X le vecteur inconnu des clics à effectuer, et B le vecteur connu des pylônes déjà allumés.

Soit les pylônes P1 à P9 représentés graphiquement par
(P1, P2, P3)
(P4, P5, P6)
(P7, P8, P9)

et qu'on utilisera ici sous la forme d'un vecteur P=t(P1, P2, P3, P4, P5, P6, P7, P8, P9)
P sert de modèle pour définir X et B.

On définit donc:
A=
(1,1,0,1,0,0,0,0,0)
(1,1,1,0,1,0,0,0,0)
(0,1,1,0,0,1,0,0,0)
(1,0,0,1,1,0,1,0,0)
(0,1,0,1,1,1,0,1,0)
(0,0,1,0,1,1,0,0,1)
(0,0,0,1,0,0,1,1,0)
(0,0,0,0,1,0,1,1,1)
(0,0,0,0,0,1,0,1,1)

Remarque: Chaque colonne représente les pylônes qui changent d'état quand on clique sur le nième pylône, où n est l'indice de la colonne.

On voit que la matrice est inversible par blocs (je vous épargne le petit calcul...); le système a donc une solution unique, et on obtient:
A^-1=
(1,0,1,0,0,1,1,1,0)
(0,0,0,0,1,0,1,1,1)
(1,0,1,1,0,0,0,1,1)
(0,0,1,0,1,1,0,0,1)
(0,1,0,1,1,1,0,1,0)
(1,0,0,1,1,0,1,0,0)
(1,1,0,0,0,1,1,0,1)
(1,1,1,0,1,0,0,0,0)
(0,1,1,1,0,0,1,0,1)

De sorte que A^-1.B=X
Chaque colonne de A^-1 représente les pylônes à cliquer pour inverser uniquement la lumière du nième pylône où n est l'indice de la colonne. Pour obtenir la solution pour un jeu de lumières donné, il suffit d'additionner les colonnes correspondantes modulo 2.