jeu des interrupteurs de Berlekamp

jeu de Berlekamp et Gale

DIDACTIQUE

Le jeu des interrupteurs de Berlekamp, ou « Berlekamp’s switching game » est un jeu inventé par Elwin R. Berlekamp et David Gale. Il est constitué d’un tableau mxm d’ampoules contrôlé par 2m interrupteurs, un pour chaque ligne et un pour chaque colonne. Quand on appuie sur un de ces interrupteurs, les ampoules concernées changent d’état : les ampoules allumées s’éteignent et les ampoules éteintes s’allument. Pour un état initial et un nombre de manipulations donnés, il s’agit de trouver le nombre minimal d’ampoules allumées. Une étude théorique conduit à des notions de théorie des codes.