Sigma-jeux sur la grille

Supposons donné un graphe dont les sommets peuvent prendre deux états, allumé ou éteint, et tel que, lorsqu'on appuie sur un sommet v, l'état des voisins de v change. Le jeu est alors le suivant : partant du graphe dont tous les sommets sont éteints, appuyer sur des sommets afin d'allumer tous les sommets du graphe. Dans quels cas peut-on y parvenir ? Et s'il est possible d'y parvenir, comment trouver la séquence d'appuis gagnante ? Nous nous intéresserons en particulier au cas de la grille et présenterons la démonstration d'une conjecture parue en 2002 dans la revue Pour la Science.