Auf einem Brett ist ein Gitter aus Lampen installiert. Eine Lampe heißt zwielichtig, wenn sie eine ungerade Anzahl leuchtender Nachbarlampen hat.
Findest du eine Konfiguration, sodass die Anzahl der zwielichtigen Lampen am Brett so groß wie möglich ist?
Einerseits ist es bei diesem kombinatorischen Rätsel erforderlich, durch geeignetes Experimentieren eine sehr gute Lösung zu finden. Man kann den Lösungsansatz systematisieren, indem man zunächst das Problem auf kleineren Brettern löst, und diese durch geeignete Konstruktionen auf größere Bretter verallgemeinert.
Insbesondere verbleibt bei dieser Aufgabe auch noch zu beweisen, dass die gefundene Lösung auch tatsächlich optimal ist. Dazu kann man beispielsweise gefinkelt eine Teilmenge der Lampen auswählen und über Paritätsargumente zeigen, dass sie nicht alle zwielichtig sein können.
Diese Aufgabe stammt von Theresia Eisenkölbl.
Zu Demonstrationszwecken hier eine kurze Begründung, warum auf einem $1\times 5$-Feld nicht alle Lampen zugleich zwielichtig sein können.
Damit die Lampen am vorderen und hinteren Ende des Bretts (also die erste und fünfte Lampe) zwielichtig sein können, müssen die zweite sowie die vierte Lampe eingeschalten sein.
Die dritte Lampe hat damit aber bereits jedenfalls zwei benachbarte eingeschaltene Lampen – und kann damit nicht mehr zwielichtig werden.