Le “Berlekamp’s switching game” - Lycée Emmanuel d'Alzon (Nîmes)

Établissement
Lycée Emmanuel d'Alzon (Nîmes)
Année
2022-2023
Résumé
Le “Berlekamp’s switching game” est un jeu inventé par Elwin R. Berlekamp et David Gale. On considère un tableau m×m ampoules et 2m interrupteurs, 1 sur chaque ligne et 1 sur chaque colonne.
Quand on actionne un interrupteur, les ampoules se trouvant sur la ligne ou la colonne correspondante et qui étaient allumés sont éteintes, et celles qui étaient éteintes sont allumés.
Le jeu consiste, pour un état initial donné, à trouver comment éteindre le plus de lampes possibles.