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