Merci pour ce superbe problème ! L'exemple est facile certes, mais le traitement du cas général m'a permis de réveiller un peu mes souvenirs d'algèbre... :-)

Oui on peut toujours tout éteindre.

En fait, ça se plonge dans un problème d'algèbre linéaire dans N/2N (arithmétique modulo 2)

Si :
* M est la matrice (nxn) d'incidence du graphe (avec une boucle en chaque sommet)
* X est le vecteur de taille n tel que : xi=1 si on bascule l'interrupteur i et 0 sinon
* déb est la configuration iniatiale (ci = 1 si la lampe i est allumée)
* fin est la configuration finale

alors savoir si on peut atteindre la configuration fin à partir de déb équivaut à résoudre le système linéaire :

             M.X + déb = fin       (dans N/2N)

pour arriver là, il faut constater que :
* l'ordre des interrupteurs n'a pas d'importance
* chaque interrupteur n'est basculé qu'au plus une fois

s'il y a plusieurs solutions, on choisit celles dont la somme (dans N cette fois) des composantes est minimale.

Trop long à expliquer mais dans le cas général, si tout est initialement allumé on peut toujours tout éteindre. Je peux donner des détails sur demande. Sauf s'il y a plus simple comme démonstration.

C'est intéressant d'entrer dans les détails ?

Pour affirmer qu'il y a toujours une solution dans ton exemple, il suffit que la matrice M soit inversible.

Elle ne l'est pas seulement si une colonne est linéairement dépendante des autres. Dans N/2N, cela revient à dire qu'une colonne est EGALE à la somme des plusieurs autres, ce qui signifie que le comportement de l'interrupteur correspondant peut être simulé avec les autres : on peut le supprimer pour étudier la faisabilité. Donc on peut toujours se ramener au cas d'une matrice inversible.

Je suis très intéressé par une approche moins "algébrique" :-D si vous avez ça ...

Cordialement,

o.

oops, je viens de m'apercevoir que ma solution ci-dessus est fausse...B+F ou B+G sont effectivement les solutions.

Une démonstration du bonus sans algèbre linéaire , par l’absurde , en raisonnant sur la parité du nombre d’ampoules .

Remarquons d’abord que le problème est équivalent à celui disant que dans tout circuit on peut  inverser l’état de chaque ampoule  . Supposons qu’il existe un système de "n+1" ampoules qu’on ne puisse pas inverser , alors il en existe un avec "n" minimum .

Considérons ce système minimum à "n+1" ampoules et retirons une des ampoules  , comme "n" est minimum , on pourrait manœuvrer pour inverser toutes les ampoules restantes . Remettons l’ampoule et effectuons les mêmes manœuvres , nous inversons alors toutes les ampoules sauf l’ampoule préalablement retirée ( n’oublions pas que nous avons supposé qu’on ne pouvait pas inverser l’état de toutes les ampoules ) . Désignons cette manipulation par "distinguer" l’ampoule ( celle qu’on retire puis qu'on remet ) , on peut "distinguer" toutes les ampoules du système .

1°) Supposons que "n+1" est pair :

On "distingue" successivement chacune des ampoules . Comme on fait la manœuvre un nombre pair de fois chaque ampoule change d'état : contradiction .

2°) Supposons que "n+1" est impair :

Il est bien connu qu’il existe un nombre pair d’ampoules ayant un nombre impairs de voisines et comme "n+1" est impair , il existe une ampoule "A" ayant un nombre pair de voisines  . "Distinguons" toutes les ampoules du système sauf "A" et ses voisines . Comme le nombre d’ampoules "distinguées" est pair , elles ont toutes changé d’état alors que "A" et ses voisines sont restées dans le même état . Il suffit d’actionner l’interrupteur "A" pour finir d’inverser toutes les ampoules : contradiction .

On peut donc inverser tout système d’ampoules .

Vasimolo

Bon , je n'ai pas la réponse à ton problème franck , d'ailleurs les solutions proposées ne sont pas "constructivistes" et je ne suis pas sûr que la stratégie proposé par gasole fonctionne vraiment ( en fait je suis quasiment sûr du contraire )

Mais bon tu as deux démonstrations qui prouvent qu'on peut toujours éteindre la lumière alors ...

Bonne nuit

Vasimolo

Bravo Mathias !

Jolie preuve.

En fait on peut la prouver directement par récurrence sans commencer par l'absurde en suivant le même schéma.

Si il n'y a qu'un interrupteur : trivial
Si il y a n>1 interrupteurs :
   - si il y en a un nombre pair : on considère chaque sous ensemble de n-1 interrupteurs. Par récurrence, on peut inverser chaque sous ensemble.  Si une de ces inversions inverse aussi l'interrupteur mis de coté, on a notre inversion pour n. Sinon notre inversion pour n est la composition de toutes ces inversions.
   - si il y en a un nombre impair : alors il existe au moins une ampoule A qui a un nombre pair de voisines. On considère chaque sous ensemble qui contient toutes les ampoules sauf une parmi A et ses voisines. Si un de ces sous-ensemble inverse aussi l'ampoule mise de coté on a notre inversion pour les n, sinon notre inversion est la composition de toutes ces sous-inversions.

Il nous resterait a avoir une preuve constructive de "alors il existe au moins une ampoule A qui a un nombre pair de voisines" et on a un algorithme pour éteindre nos ampoules