23: Lichtermeer / Sea of Lights

    Ähnlich wie man schnell binäre Zahlen untereinanderschreiben kann (Bit ganz rechts immer 0,1,0,1.., links daneben 0,0,1,1,... dann 4 er-Blöcke und 8 er-Blöcke..) kann man Repräsentantion jeder der Zahlen 1 bis 2020 finden, indem man immer etwa die Hälfte aller Schalter umlegt, nur eben in anderen Konstellationen, sodass man auf ceil(log2 2020) = 11 kommt. Damit lässt sich das Problem auch für verschieden Schalterstellungen k und Lampen n mit floor(logk n) lösen.

    Für n = 1 gilt notwendigerweise, dass gar nicht geschälten werden muss, was auch realistisch ist, bei n = 2 aber schon einmal. So kann man sich auch induktiv ranarbeiten.

    Eine Möglichkeit um die umzulegenden Schalter explizit zu beschreiben: Beim i-ten Gang schaltet man genau die Schalter an, deren Nummer in der Binärdarstellung an Stelle i eine 1 hat.

    Nach 11 Kellergängen hat man dann für jede Lampe eine Folge von an/aus Zuständen: die bildet gerade die 11-stellige Binärdarstellung der Nummer des zugehörigen Schalters.

    hg1 schrieb:

    Eine Möglichkeit um die umzulegenden Schalter explizit zu beschreiben: Beim i-ten Gang schaltet man genau die Schalter an, deren Nummer in der Binärdarstellung an Stelle i eine 1 hat

    Naja, ich hab es genau umgekehrt gemacht, ich hatte immer alle Schalter an und hab nur bestimmte (so wie du beschrieben hast, binärcodiert) ausgeschaltet, kommt aber im Ergebnis natürlich aufs Gleiche raus.

    Schalter und Lampen "schreien" ja quasi nach einer Binärcodierung. Und da man mit 11 Stellen 2^11 = 2048 Zahlen darstellen kann, genügen 11 Gänge in den Keller. Man kann die Situation sich auch mit 4, 8 Lampen und 16 Lampen konkret aufzeichnen und erkennt dann, dass hier eigentlich das Pascalsche Dreieck eine Rolle spielt.