Bonjour,

E puis A. C'est si simple que je ne dois pas avoir compris...

Coupe le jus au compteur directement !
Sinon, je pense que ce qui était valable sur le problème de Yanneck l'est aussi ici (on fait des systèmes d'équation XOR et on résout ce système)

Dans ton exemple, ça donne
A XOR B XOR C = 1
B XOR A XOR C XOR D = 1
C XOR A XOR B XOR D XOR E = 1
D XOR B XOR C XOR E = 1
E XOR C XOR D XOR F XOR G = 1
F XOR E XOR G = 1
G XOR E XOR F = 1

=> D = 0
=> E = 0
=> B XOR C = 1 => A =0
=> F XOR G = 1 => C = 0 => B =1

Conclusion, on appuie sur B et sur F ou G au choix.

je donne la valeur suivante aux interrupteurs:

    A B C D E F G
A = 1 1 1 0 0 0 0
B = 1 1 1 1 0 0 0
C = 1 1 1 1 1 0 0
D = 0 1 1 1 1 0 0
E = 0 0 1 1 1 1 1
F = 0 0 0 0 1 1 1
G = 0 0 0 0 1 1 1

On note immédiatement B+F ou B+G=1 1 1 1 1 1 1 c'est a dire qu'ils éteignent toutes les lampes.

aussi
F=G
C+D = A
D+E+F=B
A+B+E+F=C
A+B=D
B+C=E
F et G ne sont pas commandables individuellement

Edit: subsidiairement,
Si on supprime le lien B à D, il n'y a plus rien qui va...

en appuyant sur B et G

Je ne vois pas de logique "simple" pour la question normale, par contre j'ai vite eu une idée pour la question bonus : on installe les sept ampoules en cercle. Ainsi, si elles sont initialement toutes allumées, alors on aura toujours un nombre impair d'ampoules allumées

EDIT : zut, trois ampoules à la fois et non deux (l'ampoule elle-même sera concernée quand on appuie sur son inter). Bon, ça m'apprendra à parler trop vite

Pour éteindre les lumière on appuie sur B (extinction de A,B,C et D) et F (extinction de E,F et G).

Sauf si l'interrupteur G est plus près que le F, dans ce cas on appuie sur B et G

Je vais essayer de réfléchir au bonus, mais pour l'instant rien de concluant...

Flying_pyros propose sans conviction le contre-exemple suivant :



Alors peut-on tout éteindre ?

Vasimolo

Pour le bonus, je propose un arbre de Steiner à quatre points.

PS : RL = LR = Le Râleur :o)

Pour le premier probleme, il s'uffit d'appuyer sur C F et G.
pour le 2eme probleme, je ne pense pas que l'on puisse tout eteindre dans la configuration de Flying_pyros.

B et F ou B et G me semblent bon

je suis parti en cherchant des interrupteurs situes a 3 liens les uns des autres quels que soient les liens par lesquels on passe. avec les symmetries que comporte le dessin, seul B convient, et le reste se deduit ensuite.

un pentagone ou chaque sommet est relie a tout le monde sauf son n+2, ca marche ?

Pour l'algorithme, je réfléchis.

Pour le bonus, si l'on a n pièces :

Le problème revient à résoudre l'équation matricielle AX=Y dans Z/2Z où A est la matrice du graphe, Y est le vecteur de (Z/2Z)^n dont tous les coefficients valent 1. et X un vecteur inconnu de (Z/2Z)^n.

(1) On remarque que A est symétrique (matrice d'un graphe non orienté) et que ses coefficients diagonaux valent 1. (chaque chaque interrupteur agit au moins sur la lampe de la pièce où il se trouve)

(2) Le système a des solutions si et seulement si toute combinaison linéaire des lignes dont le premier membre est nul a son second membre nul également.
On remarque que dans notre cas une combinaison de lignes s'écrit :
[TeX]L_{i_1}+...+L_{i_k}\quad k\in{1,...,n},\quad 1\leq i_1<i_2<...<i_k\leq n[/TeX]
En effet le seul coeff non nul disponible dans Z/2Z est 1...

(3) Le second membre d'une combinaison paire (k pair) de lignes est toujours nul (k=2m=0 dans Z/2Z). Donc une combinaison paire de ligne dont le premier membre est nul n'apporte aucune restriction.

(4) Montrons que le premier membre d'une combinaison impaire (k impair) de lignes est nécessairement non nul.
On note
[TeX]I=\{i_1,...,i_k\}[/TeX]
l'ensemble des numéros de lignes que l'on ajoute.

Formont A' la matrice carrée extraite de A dont les entrées sont définies par IxI :
[TeX]A'=\left(\begin{array}{cccc}
a_{i_1,i_1} &a_{i_1,i_2} &... &a_{i_1,i_k} \\
a_{i_2,i_1} &a_{i_2,i_2} &... &a_{i_2,i_k} \\
... &... &... &...\\
a_{i_k,i_1} &a_{i_k,i_2} &... &a_{i_k,i_k} \\
\end{array} \right)[/TeX]
Soit en tenant compte de la symétrie de A :
[TeX]A'=\left(\begin{array}{cccc}
1 &a_{i_1,i_2} &... &a_{i_1,i_k} \\
a_{i_1,i_2} &1 &... &a_{i_2,i_k} \\
... &... &1 &...\\
a_{i_1,i_k} &a_{i_2,i_k} &... &1 \\
\end{array} \right)
[/TeX]
La matrice A' est donc aussi symétrique avec des 1 sur sa diagonale. Ainsi :
[TeX]\sum_{i,j\in I}a_{ij}=\sum_{i,j\in I,i<j}a_{ij}+\sum_{i\in I}a_{ii}+\sum_{i,j\in I,i>j} a_{ij}= 2\sum_{i,j\in I,i<j}a_{ij}+\sum_{i\in I}1=0+k=1[/TeX]
car k est impair. Les sommes des coefficients des colonnes ne peuvent être toutes nulles (sinon la somme de tous les coefficients serait nul) : le premier membre d'un nombre impair de combinaison linéaires n'est jamais nul.

(5) En conclusion, les seules combinaisons de lignes qui mènent à un premier membre nul sont paires et ont un second membre nul, ainsi le système admet toujours des solutions.
Il est toujours possibles d'éteindre toutes les lampes

Joli !

c et f