Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #26 - 16-11-2010 17:27:08

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

EDF ça se compliique ( + Bonus )

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.

#0 Pub

 #27 - 16-11-2010 17:48:33

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

EDF ça se complique ( + Bonu )

Un petit état des lieux ( sauf erreur ) :

Premier problème : Medihv , Scarta , Franck , R(a)L(e) smile , Gabriel , Flying_pyros , Supercab , McFlambi , Bamby2 .

Deuxième problème : Scarta ( un peu seul )

Bonus :

Scarta a commencé à épuiser les cas : dur labeur smile

Deux démonstrations de Yannek et Gasole ( que je n'ai pas encore complètement vérifiées ) .

Courage à ceux qui cherchent encore smile

Vasimolo

Edit : je suis convaincu par la démo de Yannek , Gasole n'est pas entré dans les détails

 #28 - 17-11-2010 00:18:25

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

edf ça sr complique ( + bonus )

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.

 #29 - 17-11-2010 10:16:25

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

EDF ça se compliqu e( + Bonus )

Vasimolo a écrit:

Je n'ai pas non plus compris ton contre-exemple mais je peux t'assurer qu'il est faux smile

Si tu peux affirmer que son contre-exemple est faux sans le comprendre, alors il n'y a pas de contre-exemple.

Sinon, j'avais pensé à un pentagone avec une ampoule sur chaque sommet et une connexion pour chaque coté plus une connexion quelconque.

Mais faut dire que je n'arrive pas à éteindre la lumière de ton diagramme non plus.
Je continue.

J'ai bien une solution à donner.

Soit un interrupteur X quelconque, x=1 si X est enclenché et x=0 si X n'est pas enclenché. X = {A, B, C, D, E, F, G, H}
Pour qu'une lampe soit éteinte, il faut que la somme des interrupteurs connectés soit impaire.
Je trouve les conditions suivantes, chaque somme de la liste doit être impaire :

(A) a+b+c
(B) a+b+c+d
(C) a+b+c+d+e
(D) b+c+d+e
(E) c+d+e+f+g
(F) e+f+g
(G) e+f+g

(A) et (B) implique que d est par, càd d=0.
(A) et (B) implique que d+e est pair, càd e=0
(C) et (D) implique que a est pair, càd a=0
(E) et (F) implique que c+d est paire, càd c=o
les conditions deviennent alors:
b =1
f+g = 1

mince alors, je trouve une solution. J'étais persuadé qu'il n'y en avait pas.

Il faut enclencher les interrupteurs B et F, ou B et G.

Avec cette méthode, je trouve que mon pentagone est éteignable, mais ne le modifiant un peu je trouve un truc innéteignable (les mots sont faits pour être inventés... ou pas)
... après analyse non en fait.sad
On arrive systématiquement à un système de n équation à n inconnue avec la seule condition que chaque équation doit donner un résultat impair. Sans réussir à le démontrer, j'ai le sentiment que c'est toujours possible.

Soit A une matrice booléenne nxn symétrique B une matrice booléenne nx1 et C la matrice 1xn tel que C = (1 1 1 1 ... 1)
Il faudrait démontrer que pour toute matrice A, il existe une matrice B tel que

A.B=C

cqfd
(ce qu'il faudrait démontrer big_smile)

Je pense que la seule condition est que det(A) soit non nul.

 #30 - 17-11-2010 13:21:48

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

EDF ça s ecomplique ( + Bonus )

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


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #31 - 17-11-2010 14:39:01

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

EDF ça se complque ( + Bonus )

Pour Gasole et Milou , il est clair que la condition matrice inversible est trop forte . Il suffit d'imaginer un circuit ou toutes les ampoules sont liées entre elles pour se rendre compte qu'on peut certes tout allumer ou tout éteindre mais sans pouvoir réaliser d'autres états .

J'ai une solution sans algèbre linéaire mais il me faudra un peu plus de temps pour rédiger , ce soir j'espère smile

Vasimolo

 #32 - 17-11-2010 18:48:16

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

EF ça se complique ( + Bonus )

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

 #33 - 17-11-2010 22:29:04

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

rdf ça se complique ( + bonus )

Je ne voudrais pas insister mais le schéma initial sans le lien B à D n'autorise pas l'extinction de toutes les ampoules...


The proof of the pudding is in the eating.

 #34 - 17-11-2010 22:52:37

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

EDF ça se compliuqe ( + Bonus )

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 smile )

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

Bonne nuit lol

Vasimolo

 #35 - 17-11-2010 23:31:07

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

EDF ça se omplique ( + Bonus )

franck9525 a écrit:

Je ne voudrais pas insister mais le schéma initial sans le lien B à D n'autorise pas l'extinction de toutes les ampoules...

CDE, je pense smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #36 - 18-11-2010 06:53:19

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

zdf ça se complique ( + bonus )

Bravo Mathias !


The proof of the pudding is in the eating.

 #37 - 18-11-2010 08:56:47

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

zdf ça se complique ( + bonus )

MthS-MlndN a écrit:

franck9525 a écrit:

Je ne voudrais pas insister mais le schéma initial sans le lien B à D n'autorise pas l'extinction de toutes les ampoules...

CDE, je pense smile

Il y a aussi:

ABCDE
ABCDEFG ! smile
CDEFG

 #38 - 18-11-2010 12:28:13

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

DEF ça se complique ( + Bonus )

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

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)
Va et vient 3 interrupteurs (37) — Schema electrique va et vient 3 interrupteurs (19) — Schema va et vient 3 interrupteurs (8) — Devinette complique (7) — Schema va et vient 3 interrupteur (7) — Branchement va et vient 3 interrupteurs (5) — Va et vient 3 interrupteur (5) — Comment faire un va et vient avec 3 interrupteurs (4) — Enigme edf (4) — Montage va et vient 3 interrupteurs (4) — Cablage va et vient 3 interrupteurs (4) — Va et vient 3 interrupteurs 2 lampes (4) — Comment brancher 3 interrupteurs va et vient (3) — Yannek (2) — Enigme interrupteurs matrice (2) — Enigme edf math (2) — Va et vient 4 interrupteurs (2) — Schema vas et vient 3 interrupteurs (2) — Jeux d ampoule matrice algebre (2) — Devinette sur edf (2) — Enigmes mathematiques compliquees (2) — Va et vient 3 points (2) — Enigme math algebre lineaire (2) — Circuit va et vient 3 interrupteurs (2) — Enigme complique (2) — Schima va et vient amiricain (2) — Model de schema de va-et-vient americain avec 3 interrupteur (2) — Calcul tres comppliquer (2) — Cablage va et vient (2) — Algebre+lineaire+enigme (1) — Schema electrique commutateur (1) — Schema electrique va et vient 4 interrupteurs (1) — Cas edf (1) — Branchement de trois interrupteurs a trois lampes (1) — Brancher interrupteur abcdefg (1) — Commander une lampe avec 3 interrupteurs (1) — Vas et viens 3 interrupteur (1) — Solution enigme tout ce qui ne touche pas touche et tout ce qui touche ne touche pas (1) — Enigme compliqu2 (1) — Steiner-hexagone (1) — Cablage de trois interrupteurs (1) — Cablage 3 inter en va et vient (1) — Branchement de trois va et vient (1) — Devinette edf (1) — Electricite va et vient 3 interrupteurs (1) — Enigme maison edf (1) — Enigme tres complique (1) — Les+equations+compiquer+en+mathematique (1) — Enimgme edf (1) — Branchement va et vient (1) — Devinettes sur edf (1) — Euromillions (1) — Schema circuit va et vient (1) — Va et vient 3 point (1) — Installation 3 interrupteurs va et vient (1) — Enigme 3 interrupteurs 1 lampe (1) — Enigmes edf (1) — Schema electrique 1 lampe 3 interrupteurs (1) — Devinette tres complique (1) — 23=15+2+6 (1) — Enigme 3 interrupteur 3 ampoules relier (1) — A xor b xor c solution (1) — Branchement trois interrupteur (1) — Devinette compliker (1) — Graphe non oriente + ampoules (1) — Algebre lineaire commutateur jeu (1) — Branchement va et vient avec 3 interrupteurs (1) — Solution 100 lampes eteintes (1) — Branchement plusieurs va et vient (1) — Branchement trois va et vient avec une ampoule (1) — Systeme va et vient pour 3 interrupteur (1) — Math algebre (1) — Enigme graphe interrupeteurs lampe matrice (1) — Schema electrique va et vient trois interrupteur (1) — Enigme compluque (1) — Syst?me d ?quation (1) — Enigme compliquee (1) — Un systeme de n equation a n inconnue (1) — Comment installer 4 va-et-vient (1) — Arbre steiner hexagone (1) — Mathematiques compliquees (1) — Schema 4 va et vient (1) — Va et vient 3 interrupteurs 1 lampe (1) — Enigme: 4 interrupteurs 1 ampoule (1) — Solution enigme edf (1) — Arbre de steiner hexagone (1) — Brancher une lampe avec 4 interupteur va et vien (1) — Branchement va et vient a 3 interrupteurs (1) — Va et vient trois interrupteur (1) — Enigme lineaire (1) — Schema va et vient (1) — Comment brancher trois interrupteur va et vient (1) — Enigme et algebre lineaire (1) — Enigme quatre interrupteurs ampoule (1) — Schema electrique avec 3 interrupteurs (1) — Branchement de trois interrupteurs (1) — Enigmes mathematiques et algebre lineaire (1) — Enigme ca touche ca touche pas (1) — Equation compliquee (1) — Ampoule et algebre (1) — Brancher 3 interrupteur en va et vient (1) — Installation 3 lampes avec 3 va et vient (1) — Cablage va et vient 3 points (1) — Jeu logique relier maison edf (1) — Resoudre un systeme a xor b = c (1) — Restriction edf ampoule marche pas (1) — Schema electrique trois interupteur 1 ampoule (1) — Va et vient a trois interrupteurs (1) — Schema va et vient 3 interrupteurs 2 lampes (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete