Ich habe überlegt, wie man jede Lampe einzeln anschalten kann, wenn alle aus sind. (Damit kann man sie dann auch einzeln ausschalten, wenn sie erst mal an sind…)
Bei 7 Lampen L1 bis L7:
L1: L4 (alle an) & L5 (L2-L7 wieder aus)
L2: L5 (L2-L7 an) & L6 (L3-L7 wieder aus)
L3: L6 (L3-L7 an) & L7 (L4-L7 wieder aus)
L4: L1 (L1-L4 an) & L7 (L4 wieder aus, L5-L7 an) & L4 (L4 wieder an, alle anderen wieder aus)
L5 - L7: analog L1 - L3, nur von der anderen Seite)
Bei 8 Lampen L1 bis L8:
L1 oder L8: L1 & L8 (alle an), dann L5 bzw. L4 (alle außer L1 bzw. L8 wieder aus)
L2 - L7: analog 7 Lampen oben, also zB. L4 & L3 für L7 an
Für 14, 15, 21, 22, etc. (also 7+k*7 und 8+k*7) Lampen habe ich’s mir ehrlich gesagt gar nicht erst überlegt. Und für 9+k*7, 10+k*7, …, 13+k*7 Lampen ebenfalls nicht…
Ich hatte vor längerer Zeit eine Diplomarbeit gelesen, und habe einen Satz daraus verwendet. "Wenn man die adjacency-matrix invertieren kann, gibt es eine Lösung". Das stimmt zwar andersrum nicht, aber für dieses Beispiel gab es in genau zwei Fällen keine invertierbare matrix. Und dann hab ich diese nicht weiter untersucht. War ja aus den Antwortmöglichkeiten klar, dass das nicht bringen wird.
Ich hoffe, dass der link so funktioniert:
Rebecca Meyer (a master's thesis) https://dc.ewu.edu/cgi/viewcontent.cgi?r...ext=theses
(01-01-2024, 10:23 AM)Raaadi schrieb: Ich habe überlegt, wie man jede Lampe einzeln anschalten kann, wenn alle aus sind. (Damit kann man sie dann auch einzeln ausschalten, wenn sie erst mal an sind…)
Bei 7 Lampen L1 bis L7:
L1: L4 (alle an) & L5 (L2-L7 wieder aus)
L2: L5 (L2-L7 an) & L6 (L3-L7 wieder aus)
L3: L6 (L3-L7 an) & L7 (L4-L7 wieder aus)
L4: L1 (L1-L4 an) & L7 (L4 wieder aus, L5-L7 an) & L4 (L4 wieder an, alle anderen wieder aus)
L5 - L7: analog L1 - L3, nur von der anderen Seite)
Bei 8 Lampen L1 bis L8:
L1 oder L8: L1 & L8 (alle an), dann L5 bzw. L4 (alle außer L1 bzw. L8 wieder aus)
L2 - L7: analog 7 Lampen oben, also zB. L4 & L3 für L7 an
Für 14, 15, 21, 22, etc. (also 7+k*7 und 8+k*7) Lampen habe ich’s mir ehrlich gesagt gar nicht erst überlegt. Und für 9+k*7, 10+k*7, …, 13+k*7 Lampen ebenfalls nicht…
Ziemlich genau so sah meine Lösung auch aus, bei 7 und 8 gibt es für jedes einzelne Lämpchen eine Sequenz, mit der ich genau dieses Lämpchen schalten kann. Das beweist zwar nicht, dass es für n*7+0 und n*7+1 immer geht, aber zumindest sind alle anderen Lösungen damit ausgeschlossen, wenn ich für Rest 0 und Rest 1 jeweils eine Lösung kenne...
Meine Lösung ist etwas umfangreicher (ich glaube auch, dass es kein vollständiges Argument ist, dass man jede Lampe an oder ausschalten kann, denn einige anderen Lampen ändern ja beim letzten Schalterdruck ihren Zustand).
Fall 1: n = 7
Man kann an einem Ende mit einem Schalterdruck auf jeden Fall eine 1 erzeugen (falls da noch keine ist). Sagen wir mal rechts am Ende (also Lampe 7) ist eine 1. Dann kann man auf jeden Fall die Lampen 6,5 und 4 auch zu 1 machen, indem man immer weiter nach links geht mit dem Schaltvorgang. (Bsp: also Schalter 3 beeinflusst Lampe 7 nicht mehr, macht aber Lampe 6 an falls diese zuvor aus ist usw.)
Also muss man nur noch die "Anfangssituationen" xyz1111 betrachten. Falls x,y und z alle 1 sind ist man fertig, denn dann schaltet man alle Lampen mit Schalter 4 aus. Falls x,y und z alle 0 sind ist man auch fertig. Dann drückt man auf Schalter 7 und alle Lampen sind aus. Man muss also nur noch sechs Fälle durch spielen:
110; 101; 100 ; 011 ; 001 und 010.
Somit geht es bei 7 immer.
Jetzt muss man zeigen, dass es dann auch bei n = k*7 geht. Also erzeugt man 7*(k-1)+4 Einsen von rechts her. Dann hat man auf den ersten drei Lampen wieder die sechs Fälle und schaltet wie oben. Allerdings beeinflusst man dadurch auch die Lampen 8 bis max. 10. Das macht aber nichts, denn hinter Lampe 10 wird nichts mehr verändert. Also setzt man wie oben, alle Lampen 1 bis 7 auf 0. Dann haben die Lampen 8 bis 10 ebenfalls eine der 6 Anfangssituationen und die Lampen 11 bis 14 stehen alle auf 1. Also geht man jetzt mit den Lampen 8 bis 14, genauso vor wie oben beschrieben (also S(i+7)).
Dieses Verfahren kann man beliebig oft durchführen ==> k*7 geht immer.
Damit sind die Antworten 1, 2, 4, 5, 6, 7 und 10 "ausgeschaltet" (also raus).
Fall 2: n = 8
Wenn man 8 Einsen hat schaltet man 4 Lampen mit Schalter 1 und 4 Lampen mit Schalter 8 aus.
Man kann wieder 5 Einsen auf den Lampen 4 bis 8 erzeugen (siehe Fall 1). Dann hat man wieder die 6 Fälle. (00011111 schaltet man ja mit S7 aus). 00111111 S6 ==> fertig 01111111 S5 ==> fertig 01011111 S6 ==> 01100000 S7 ==> 01111111 S5 ==> fertig 10011111 S5 ==> 11100000 S7 ==> 11111111 S1 und S8 ==> fertig 10111111 S5 ==> 11000000 S6 ==> 11111111 S1 und S8 ==> fertig 11011111 S6 ==> 11100000 S7 ==> 11111111 S1 und S8 ==> fertig
Also eine 8 bekommt man immer weg.
Jetzt muss man noch die 7*k+1 =7*(k-1)+8 betrachten. Bsp. k=2: Man erledigt zuerst die Lampen 1 bis 8 wie oben beschrieben. Dabei verändert man höchstens die Lampen 9 bis 11. Die Lampen 12 bis 15 bleiben Einsen. Also haben wir wieder die Problematik wie bei 7 Lampen, also xyz1111 und das wurde bereits gelöst. Wenn k>=3 ist, dann erledigt man immer zuerst den Achter und dann alle folgenden Siebener.
Also geht 1 mod 7 ebenfalls immer.
Antwort 8 ist also richtig.
Anmerkung: Bei n = 9 bekommt man die Anfangsbedingung 0 1111 1111 nicht ausgeschaltet. Wenn man die 8 Einsen ausschaltet von rechts und von links schaltet man die Lampe 1 wieder an.
Bei dieser Aufgabe konnte ich meine längst verschütteten Kenntnisse in Gruppentheorie auffrischen. Die Lampenkonfigurationen bilden zusammen mit dem logischen XOR eine Gruppe. Dann muss man nur untersuchen, ob die Schaltvorgänge ausreichen, um die komplette Gruppe zu erzeugen. Der komplette Beweis unter:
(01-02-2024, 10:05 AM)st1974 schrieb: Bei dieser Aufgabe konnte ich meine längst verschütteten Kenntnisse in Gruppentheorie auffrischen. Die Lampenkonfigurationen bilden zusammen mit dem logischen XOR eine Gruppe. Dann muss man nur untersuchen, ob die Schaltvorgänge ausreichen, um die komplette Gruppe zu erzeugen. Der komplette Beweis unter:
Vielen Dank für die sehr schön geschriebene Lösung!
Nur eine kleine Anmerkung: Es scheint mir so, als wäre G_n hier nicht nur eine Gruppe sondern sogar ein Vektorraum, genauer gesagt der n-dimensionale Vektorraum über dem 2-elementigen Körper {0,1} (mit 1+1=0). Denn man kann sich die Elemente von G_n ja als Vektoren über {0,1} der Länge n mit komponentenweiser Addition vorstellen.
Deshalb kann man lineare Algebra anwenden - das von dir benutzte Verfahren ist also genau das Gaußschen Eliminationsverfahren in der linearen Algebra
(Und aus der Diagonalform folgt, dass die Matrix invertierbar ist, also vollen Rang hat weshalb die Zeilenvektoren den ganzen Raum aufspannen)
(01-02-2024, 10:05 AM)st1974 schrieb: Bei dieser Aufgabe konnte ich meine längst verschütteten Kenntnisse in Gruppentheorie auffrischen. Die Lampenkonfigurationen bilden zusammen mit dem logischen XOR eine Gruppe. Dann muss man nur untersuchen, ob die Schaltvorgänge ausreichen, um die komplette Gruppe zu erzeugen. Der komplette Beweis unter:
Vielen Dank für die sehr schön geschriebene Lösung!
Nur eine kleine Anmerkung: Es scheint mir so, als wäre G_n hier nicht nur eine Gruppe sondern sogar ein Vektorraum, genauer gesagt der n-dimensionale Vektorraum über dem 2-elementigen Körper {0,1} (mit 1+1=0). Denn man kann sich die Elemente von G_n ja als Vektoren über {0,1} der Länge n mit komponentenweiser Addition vorstellen.
Deshalb kann man lineare Algebra anwenden - das von dir benutzte Verfahren ist also genau das Gaußschen Eliminationsverfahren in der linearen Algebra
(Und aus der Diagonalform folgt, dass die Matrix invertierbar ist, also vollen Rang hat weshalb die Zeilenvektoren den ganzen Raum aufspannen)
Danke für die Einordnung für als n-dimensionaler Vektorraum. Dann ist klar, dass der Gaußsche Eliminationsalgorithmus anwendbar ist.
(01-01-2024, 09:24 PM)Mathe Juergen schrieb: (ich glaube auch, dass es kein vollständiges Argument ist, dass man jede Lampe an oder ausschalten kann, denn einige anderen Lampen ändern ja beim letzten Schalterdruck ihren Zustand).
Ich denke schon, dass dieses Argument vollständig ist. Wenn man alle möglichen Schaltzustände der n Lampen als Ecken eines n-dimensionalen Hyperwürfels betrachtet, dann sind die Umschaltungen der einzelnen n Lampen eine linear unabhängige Basis.
Mein Ansatz war aber ein ganz anderer, denn ich habe auch diese Aufgabe programmiert.
Ein Schalter schaltet den Zustand bestimmer Glühbirnen um. Er entspricht einem n-Tupel.
Eine Glühbirne an Position i wird umgeschaltet, falls der i-te Eintrag des n-Tupels 1 ist,
und nicht umgeschaltet, falls der i-te Eintrag 0 ist.
Eine Schaltfolge ist die Hintereinanderausführung einer Menge von Schaltern, die genau einmal betätigt werden. Die Reihenfolge der Schalterbetätigungen spielt keine Rolle.
Das Ergebnis (Umschaltwirkung) entspricht dem exklusiven Odern der entsprechenden n-Tupel und ist selbst auch ein n-Tupel.
Es gibt genau 2^n mögliche unterschiedliche Anfangszustände der n Glühbirnen.
Mit n Schaltern können genau 2^n verschiedene Schaltfolgen ausgeführt werden. Eine Schaltfolge ist ein Element der Potenzmenge der Menge der n Schalter.
Idee:
Um alle 2^n Anfangszustände ausschalten zu können, dürfen keine zwei Schaltfolgen das gleiche bewirken.
Bei 9 Glühbirnen führen die Schaltfolgen { 1, 9 } und { 2, 8 } zum gleichen Ergebnis. <==> Schaltfolge { 1, 2, 8, 9 } entspricht der leeren Schaltfolge {}, ändert also nichts.
==> Es können nicht alle Zustände ausgeschaltet werden.
Untersuche 7 Glühbirnen:
0 mod 7 ist möglich.
Time (s): 0.007
Untersuche 8 Glühbirnen:
1 mod 7 ist möglich.
Time (s): 0.007
Untersuche 9 Glühbirnen:
2 mod 7 ist nicht möglich.
Index 495 erneut gefunden bei Schaltfolge 2 8
Index 495 zuerst gefunden bei Schaltfolge 1 9
Time (s): 0.008
Untersuche 10 Glühbirnen:
3 mod 7 ist nicht möglich.
Index 1007 erneut gefunden bei Schaltfolge 2 8
Index 1007 zuerst gefunden bei Schaltfolge 1 9
Time (s): 0.01
Untersuche 11 Glühbirnen:
4 mod 7 ist nicht möglich.
Index 2031 erneut gefunden bei Schaltfolge 2 8
Index 2031 zuerst gefunden bei Schaltfolge 1 9
Time (s): 0.012
Untersuche 12 Glühbirnen:
5 mod 7 ist nicht möglich.
Index 4063 erneut gefunden bei Schaltfolge 3 9
Index 4063 zuerst gefunden bei Schaltfolge 2 10
Time (s): 0.009
Untersuche 13 Glühbirnen:
6 mod 7 ist nicht möglich.
Index 8127 erneut gefunden bei Schaltfolge 4 10
Index 8127 zuerst gefunden bei Schaltfolge 3 11
Time (s): 0.009
Untersuche 14 Glühbirnen:
0 mod 7 ist möglich.
Time (s): 0.051
Untersuche 15 Glühbirnen:
1 mod 7 ist möglich.
Time (s): 0.118
Untersuche 16 Glühbirnen:
2 mod 7 ist nicht möglich.
Index 2063 erneut gefunden bei Schaltfolge 2 8 9
Index 2063 zuerst gefunden bei Schaltfolge 1 15 16
Time (s): 0.05
Untersuche 17 Glühbirnen:
3 mod 7 ist nicht möglich.
Index 2063 erneut gefunden bei Schaltfolge 2 8 9
Index 2063 zuerst gefunden bei Schaltfolge 1 15 16
Time (s): 0.007
Untersuche 18 Glühbirnen:
4 mod 7 ist nicht möglich.
Index 2063 erneut gefunden bei Schaltfolge 2 8 9
Index 2063 zuerst gefunden bei Schaltfolge 1 15 16
Time (s): 0.011
Untersuche 19 Glühbirnen:
5 mod 7 ist nicht möglich.
Index 4127 erneut gefunden bei Schaltfolge 3 9 10
Index 4127 zuerst gefunden bei Schaltfolge 2 16 17
Time (s): 0.066
Untersuche 20 Glühbirnen:
6 mod 7 ist nicht möglich.
Index 8255 erneut gefunden bei Schaltfolge 4 10 11
Index 8255 zuerst gefunden bei Schaltfolge 3 17 18
Time (s): 0.015
Untersuche 21 Glühbirnen:
0 mod 7 ist möglich.
Time (s): 2.964
Untersuche 22 Glühbirnen:
1 mod 7 ist möglich.
Time (s): 6.624
Untersuche 23 Glühbirnen:
2 mod 7 ist nicht möglich.
Index 258063 erneut gefunden bei Schaltfolge 2 8 9 15
Index 258063 zuerst gefunden bei Schaltfolge 1 16 22 23
Time (s): 0.013
Untersuche 24 Glühbirnen:
3 mod 7 ist nicht möglich.
Index 258063 erneut gefunden bei Schaltfolge 2 8 9 15
Index 258063 zuerst gefunden bei Schaltfolge 1 16 22 23
Time (s): 0.013
Untersuche 25 Glühbirnen:
4 mod 7 ist nicht möglich.
Index 258063 erneut gefunden bei Schaltfolge 2 8 9 15
Index 258063 zuerst gefunden bei Schaltfolge 1 16 22 23
Time (s): 0.016
Untersuche 26 Glühbirnen:
5 mod 7 ist nicht möglich.
Index 516127 erneut gefunden bei Schaltfolge 3 9 10 16
Index 516127 zuerst gefunden bei Schaltfolge 2 17 23 24
Time (s): 0.019
Untersuche 27 Glühbirnen:
6 mod 7 ist nicht möglich.
Index 1032255 erneut gefunden bei Schaltfolge 4 10 11 17
Index 1032255 zuerst gefunden bei Schaltfolge 3 18 24 25
Time (s): 0.027
Total Time (s): 10.091
Genau für die Werte von n >= 7, die bei der Division durch 7 den Rest 0 oder 1 haben. -> Antwort 8
