Problème proposé par Christian Romon

Je dispose d'une guirlande de 2ⁿ (n>0) lampes en forme de boucle refermée sur elle-même. En position initiale un certain nombre d'entre elles ont été allumées de façon aléatoire.
J'ai un dispositif de commande qui effectue simultanément sur toutes les lampes l'opération suivante :
-position allumée pour toutes les lampes comprises entre une lampe allumée et une lampe éteinte.
- position éteinte sinon (i.e. lampe comprise entre deux lampes éteintes ou entre deux lampes allumées).
Quel est le nombre minimal N de commandes qui me garantit l'extinction complète de toutes les lampes ?
Donner une caractérisation simple des positions initiales "maximales" c'est-à-dire nécessitant effectivement d'effectuer le nombre de commandes N précédemment trouvé pour tout éteindre.

 Solution