Pivot de Gauss et extinction des feux

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Nathalie.Roche
Membre Naturel
Messages: 10
Enregistré le: 12 Mai 2008, 13:08

pivot de Gauss et extinction des feux

par Nathalie.Roche » 12 Mai 2008, 13:26

A la page suivante :
http://ljk.imag.fr/membres/Bernard.Ycart/mel/sl/node16.html
une intéressante application de la méthode de résolution d'un système par le pivot de Gauss.

Il y a un truc qui m'échappe :cry: : il me semble que dans l'interprétation, l'état initial du graphe (tout est éteint) n'est pas pris en compte. Or une même solution du système ne sera pas une solution au problème si par exemple quelques sommets sont allumés...

Si quelqu'un comprend mon pb et a une explication, merci d'avance.



ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 12 Mai 2008, 14:33

Si,l état initial est pris en compte bien sur. Dans leur exemple disons,la premiere ligne x1+x2+x5 represente le changement d etat de la premiere ampoule.Si x1+x2+x5=1,alors ca signifie que si elle était eteinte elle devient allumée,et si elle était allumée elle devient eteinte.Ainsi leur systeme d equations modelise le fait de faire changer toutes les ampoules d etats.En particulier,si elles sont toutes eteintes elles deviennent toutes allumées..Ché pas si je suis clair

Mais merci pour le lien sinon,c est cool comme demo.Un pote m avais deja démontrer ce truc,mais en bien plus abstrait,avec des histoires d orthogonaux dans Z/2Z.Au final ct la meme demo je crois,mais la avec pivot de gauss c est limpide..

Nathalie.Roche
Membre Naturel
Messages: 10
Enregistré le: 12 Mai 2008, 13:08

par Nathalie.Roche » 12 Mai 2008, 15:07

Merci. J'interprètais le 1 comme "ampoule allumée". Si on l'interprète plutôt par "changement d'état", c'est plus clair.

Nathalie.Roche
Membre Naturel
Messages: 10
Enregistré le: 12 Mai 2008, 13:08

par Nathalie.Roche » 12 Mai 2008, 18:21

Je viens de tomber sur la page suivante qui donne d'autres arguments intéressants :

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=5976


Dans la preuve suivante :

Use induction. assume its true for n-1.

Now, there are 2^n possible states of color, and each point can be either "switched" or not, giving 2^n possible sequences of operations. Therefore, if we cannot get them all black, there must be a set S of k points such that switching every point in S causes no change. Now, each point in S is connected to an even number of points in S, so each point in S has an odd number of neighbours in S. So |S| is even. Now, as each point is connected to an even number of points in S, the number of white vertices in S never changes parity mod 2. Now, fix a vertex V in S. If we can get all points except for V black, then V must also be black due to our parity argument. But this is doable by induction. Hence, result.

je ne comprends pas du tout l'affirmation : "if we cannot get them all black, there must be a set S of k points such that switching every point in S causes no change. "

Si quelqu'un peut m'éclairer sur ce point, merci.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 77 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite