The Berlekamp’s switching game - Lycée Bellevue (Alès) Colegiul National Mihail Eminescu (Satu Mare - Roumanie)

Titre du sujet
The Berlekamp’s switching game
Établissement
Lycée Bellevue (Alès)
Année
2019-2020
Etablissement(s) jumelé(s)
Colegiul National Mihail Eminescu (Satu Mare - Roumanie)
Résumé
The ''Berkelamp's switching game'' was a game invented by Elwin R. Berkelamp and David Gale.
We consider a table m x m light bulbs and 2m light switches, 1 on each line and 1 on each column of the table.
Whenever we activate a switch, the light bulbs that are on the corresponding line or on the corresponding column and were switched on are then switched off, and those that were off are on.
The game consists, for a given initial state, in finding out how to switch off as many bulbs as possible.