Auf einem Drehteller sind ganz regelmäßig und symmetrisch vier Schalter montiert. Man kann die Schalter nicht voneinander unterscheiden - insbesondere kann ich die Schalter im Vergleich zu vorher nicht mehr eindeutig identifizieren, wenn jemand den Drehteller gedreht hat. Auch von der Verkabelung sehe ich nichts und auch nicht, ob ein Schalter ein- oder ausgeschaltet ist. Genau genommen sieht der Schalter eben äußerlich (also für uns) genau gleich aus, egal ob er den Zustand "an" oder "aus" hat. Kurzum: Durch Schalten verändere ich den Zustand von "an" zu "aus" oder von "aus" zu "an", aber ich sehe nicht, ob Ersteres oder Letzteres. Die vier Schalter sind in Reihe geschaltet mit einer Glühbirne im Nachbarraum verbunden, d.h. die Lampe im Nachbarraum leuchtet nur dann, wenn alle vier Schalter auf "an" stehen. Ich kenne den Anfangszustand nicht, weiß nur, dass im Moment die Lampe im Nachbarraum noch nicht leuchtet.
In einem Schritt darf ich beliebig viele der vier Schalter bedienen und kann nach (!) diesen Schalterbedienungen schließlich nachsehen, ob die Lampe im Nachbarraum brennt. (Dazwischen nachschauen ist nicht drin... erst am Ende des Schritts!!) Erneut die Schalterstellung(en) ändern darf ich erst im nächsten Schritt. Und vor diesem nächsten Schritt darf ein Fremder den Drehteller verdrehen, wie er will, ohne, dass ich das beobachte.
Wie viele Schritte brauche ich mindestens, um SICHER (das heißt auch bei ungünstigsten/beliebigen Anfangsbedingungen und ungünstigstem/beliebigem Verdrehen) die Lampe im Nachbarraum zum Leuchten zu bringen?
Anmerkung: Ich behalte mir vor, vor der Bewertung von Einzelnen per logic-weekly-Nachricht Begründungen für ihre Lösung nachzufordern und davon die Richtig/Falsch-Wertung abhängig zu machen.
Zu allererst mal die Idee, die man leichter nachvollziehen kann, wenn man zunächst nur 2 Schalter betrachtet. Angenommen beide Schalter sind anfangs aus... dann ist es die richtige Idee, beide Schalter zu drücken. Dann wird die Lampe leuchten. Waren nicht beide Schalter an, sondern nur einer (und der andere aus), habe ich durch das "beide Schalter drücken" auch nichts kaputt gemacht: Es ist (unabhängig davon, wie der Drehteller gedreht wurde) danach wieder ein Schalter an und einer aus. Dann wäre es das richtige Konzept, jetzt irgendeinen Schalter zu drücken: Wenn ich Glück habe, habe ich den richtigen Schalter erwischt und die Lampe leuchtet - fertig. Habe ich Pech, dann habe ich durch die Aktion erreicht, dass beide Schalter aus sind. Daran verändert dann der Drehteller aber auch nichts... ... und ich kann spätestens durch diesen 3. Schritt, nämlich "beide Schalter bedienen", das Licht eischalten. Schön, oder?
Doch nun der etwas kompliziertere Fall mit 4 Lichtschaltern (mit 3 gehts nicht - s.u.):
Folgende 15 Schritte sind meine Lösung... weniger kann übrigens gar nicht gehen, weil es 2 hoch 4 = 16 verschiedene Schalterzustände gibt. Da der Ausgangszustand wegfällt, sind 15 Schaltzustände und damit 15 Schritte eine absolut richtige Abschätzung nach unten. Erstaunlich ist eher schon, dass es trotz des Drehtellers auch in 15 Schritten möglich ist:
Zu bedienen sind... 1. alle Schalter 2. irgendwelche zwei Schalter (gegenüber) 3. alle Schalter 4. irgendwelche zwei Schalter (nebeneinander) 5. alle Schalter 6. irgendwelche zwei Schalter (gegenüber) 7. alle Schalter 8. irgendeinen Schalter 9. alle Schalter 10. irgendwelche zwei Schalter (gegenüber) 11. alle Schalter 12. irgendwelche zwei Schalter (nebeneinander) 13. alle Schalter 14. irgendwelche zwei Schalter (gegenüber) 15. alle Schalter Spätestens jetzt wird die Lampe leuchten!
Begründung: Siehe Abbildung hier unten - je nach Ausgangszustand (A: kein Schalter an, B: ein Schalter an etc.) werden die möglichen Zwischenzustände nach den Aktionen aufgelistet. F bedeutet, dass alle Schalter an sind und die Untersuchung dort abgebrochen werden kann. Und dies ist spätestens beim 15. Schritt der Fall.
Übrigens: Wer 15 getippt hat, da es 2 hoch 4 Schalterzustände gibt und einer (der Anfangszustand) schon geklärt ist (als 2^4-1=15) hat zwar mathematisches Feeling bewiesen, aber eigentlich nicht recht: Da man den Schalterzustand vorher nicht kennt und nicht erkennt, ist durch das Ausprobieren aller Möglichkeiten Schalter zu betätigen trotzdem nicht gewährleistet, dass man auch alle Schaltzustände erwischt (und sich nicht wiederholt). Wer auf der Basis richtig getippt hat, hat bei der Bewertung jetzt einfach Glück gehabt...
Das Problem lässt sich übrigens für jede Zweierpotenz n (also n=2^k mit natürlichem k) von Lichtschaltern lösen und die Mindestschrittzahl ist 2^n-1.
