| Autor |
Beitrag |
    
Edi (ukrainez)
Neues Mitglied
Benutzername: ukrainez
Nummer des Beitrags: 3
Registriert: 12-2002
| | Veröffentlicht am Montag, den 09. Dezember, 2002 - 17:31: | 
|
Hallo,
ich muß folgende Aufgabe beweisen, finde aber keinen Ansatz, wer kann helfen?
Es seien 7 Lampen kreisförmig angeordnet. An jeder Lampe ist ein Schalter, der diese Lampe und ihre beiden Nachbarn schaltet, also jeweils vom ein- in den ausgeschalteten Zustand bzw. umgekehrt versetzt. Beweisen Sie: Bei beliebigem Anfangszustand kann man durch Schalten stets erreichen, dass alle Lampen angeschaltet sind.
Durch Ausprobieren ist es klar, aber wie beweist man sowas?
|
heimdall (gjallar)
Mitglied
Benutzername: gjallar
Nummer des Beitrags: 25
Registriert: 11-2002
| | Veröffentlicht am Dienstag, den 10. Dezember, 2002 - 08:43: |
|
Hallo,
Beweis über lineares Gleichungssystem modulo 2.
Der Anfangszustand sei L, z.B. L = (1 0 0 1 1 0 1) (1=ein, 0=aus)
Die Wirkung von Schalter 1 entspricht einer Vektoraddition modulo 2 von
S1 = (1 1 0 0 0 0 1)
ebenso
S2 = (1 1 1 0 0 0 0)
S3 = (0 1 1 1 0 0 0)
S4 = (0 0 1 1 1 0 0)
S5 = (0 0 0 1 1 1 0)
S6 = (0 0 0 0 1 1 1)
S7 = (1 0 0 0 0 1 1)
Betrachte nun die Variablen xi, i=1,...,7, mit Werten 0 (Schalter i wird nicht betätigt) oder 1 (Schalter i wird betätigt). Die xi sollen die Lösungs-Schaltfolge beschreiben, die L in (1 1 1 1 1 1 1) überführt, also
L + S1*x1 + ... + S7*x7 = (1 1 1 1 1 1 1)
Das kann man nun als lineares Gleichungssystem mod 2 schreiben: M * x = L + 1
(1 1 0 0 0 0 1) (x1) (L1 + 1)
(1 1 1 0 0 0 0) (x2) (L2 + 1)
(0 1 1 1 0 0 0) (x3) (L3 + 1)
(0 0 1 1 1 0 0)*(x4)=(L4 + 1)
(0 0 0 1 1 1 0) (x5) (L5 + 1)
(0 0 0 0 1 1 1) (x6) (L6 + 1)
(1 0 0 0 0 1 1) (x7) (L7 + 1)
Die Inverse Matrix mod 2 ist leicht zu berechnen, und damit ist das Problem für jeden Anfangszustand L explizit lösbar
(1 1 0 1 1 0 1)
(1 1 1 0 1 1 0)
(0 1 1 1 0 1 1)
(1 0 1 1 1 0 1) = M-1
(1 1 0 1 1 1 0)
(0 1 1 0 1 1 1)
(1 0 1 1 0 1 1)
Im Beispiel:
M-1 * (L + 1) =
M-1 * ((1 0 0 1 1 0 1)+(1 1 1 1 1 1 1)) =
(1 1 1 1 0 1 0), d.h. Schaltfolge S1, S2, S3, S4, S6
Gruß,
Gjallar
|
|
