jeu des interrupteurs de Berlekamp

Imaginez un carré d’ampoules, chacune pouvant être allumée ou éteinte. Un interrupteur de ligne agit sur toutes les ampoules d’une même ligne ; un interrupteur de colonne agit sur toutes celles d’une même colonne. À chaque action, l’état de chaque ampoule touchée s’inverse. Deux actions sur le même interrupteur s’annulent, comme deux changements successifs qui ramènent à l’état de départ. Le jeu demande de choisir un nombre fixé d’actions pour laisser le moins d’ampoules allumées possible. Cette règle visible cache un calcul avec seulement deux états : 0 pour éteint et 1 pour allumé.

Le jeu des interrupteurs de Berlekamp est un problème combinatoire sur un tableau carré de m lignes et m colonnes, où m est un entier positif. Chaque case contient une ampoule dans l’un de deux états. Les m interrupteurs de lignes et les m interrupteurs de colonnes forment les 2m commandes du tableau. Appuyer sur un interrupteur inverse simultanément l’état de toutes les ampoules de la ligne ou de la colonne qu’il commande.

Une configuration initiale fixe l’état de chaque case. Pour un nombre de manipulations imposé, on cherche une suite d’interrupteurs qui minimise le nombre d’ampoules allumées après la dernière action. Comme inverser deux fois une même ampoule la ramène à son état initial, seuls les nombres pairs ou impairs d’actions sur chaque interrupteur importent. On peut donc coder un état par 0 ou 1 et effectuer les calculs dans le corps à deux éléments, noté F₂, où l’addition de 1 et 1 vaut 0. Cette traduction relie le jeu à l’algèbre linéaire et aux codes correcteurs d’erreurs.

Considérons un tableau 2×2, donc avec deux interrupteurs de lignes et deux interrupteurs de colonnes. Au départ, seule l’ampoule située en haut à gauche est allumée. Une seule manipulation est autorisée.

Données : 2 lignes ; 2 colonnes ; 1 ampoule allumée au départ ; 1 manipulation autorisée.

La configuration initiale se lit ligne par ligne, avec 1 pour allumée et 0 pour éteinte.

Si l’on appuie sur l’interrupteur de la première ligne, ses deux ampoules s’inversent : 1 devient 0 et 0 devient 1.

La configuration finale comporte donc 1 ampoule allumée. Pour comparaison, appuyer sur la deuxième ligne ou sur la deuxième colonne laisse 3 ampoules allumées, tandis qu’appuyer sur la première colonne en laisse aussi 1. Le minimum, pour cette unique manipulation, vaut donc 1.

Le contrôle est direct : la première ligne contient exactement un 0 et un 1, et la seconde ligne deux 0. Le comptage donne bien 1 ampoule allumée.

Pour résoudre une petite position, on dessine le tableau et on note l’état de chaque ampoule. On teste ensuite les interrupteurs autorisés, en comptant les ampoules allumées après le nombre d’actions demandé.

Pour un tableau plus grand, on remplace le dessin par une suite de 0 et de 1. L’algèbre linéaire sur F₂ devient préférable lorsque l’on veut comparer systématiquement beaucoup de configurations : l’addition modélise les inversions successives et le poids compte les ampoules allumées.

Une vérification visuelle reste utile après le calcul. Elle consiste à reprendre chaque ligne et chaque colonne modifiée, puis à contrôler l’état des cases qui ont été touchées une ou plusieurs fois.

Le jeu des interrupteurs de Berlekamp ne se confond pas avec un jeu où chaque interrupteur commande une seule ampoule. Le critère est observable : ici, une action touche toute une ligne ou toute une colonne. Dans le tableau 2×2 de l’exemple, l’interrupteur de première ligne modifie deux cases en même temps ; une commande case par case en modifierait une seule.

Il ne s’agit pas non plus simplement d’éteindre toutes les ampoules. Le nombre de manipulations est fixé, et l’objectif porte sur le nombre d’ampoules allumées à la fin. Une stratégie qui éteint davantage d’ampoules mais dépasse ce nombre d’actions ne respecte pas la règle du problème.

Le nombre de manipulations est une contrainte essentielle. Si ce nombre est nul, la configuration finale est exactement la configuration initiale : aucune commande ne peut la modifier. Si le nombre d’actions augmente, le minimum recherché peut changer ; il ne faut donc pas réutiliser sans vérification le résultat obtenu pour une autre contrainte.

Une autre difficulté vient des cases situées à l’intersection d’une ligne et d’une colonne modifiées. Elles sont inversées deux fois et retrouvent leur état initial. Compter séparément les effets d’une ligne et d’une colonne sans tenir compte de ces intersections donne un résultat faux.

Enfin, appuyer deux fois sur le même interrupteur annule son effet sur toutes les ampoules. Dans le codage par 0 et 1, cela signifie que seules la parité du nombre d’actions sur chaque interrupteur et la contrainte sur le nombre total d’actions doivent être distinguées.

Le passage des ampoules aux valeurs 0 et 1 ouvre sur une question d’algèbre linéaire. À chaque interrupteur de ligne ou de colonne, on associe un vecteur de longueur m² : il vaut 1 sur les cases inversées par cet interrupteur et 0 ailleurs. Dans F₂, additionner les vecteurs des interrupteurs choisis donne les cases inversées au total ; on l’ajoute au vecteur de la configuration initiale pour obtenir la configuration finale. Le même langage permet ensuite d’étudier le poids des configurations, c’est-à-dire le nombre de leurs coordonnées égales à 1, et explique le lien naturel avec les codes correcteurs d’erreurs.