Mathe Wiki
Registrieren
Advertisement

Dies ist die Lösung 3 von Aufgabe Gefangene und Glühbirne.

"Tage nummerieren, jeder zählt":

Jeder Gefangene erhält eine Nummer von 1 bis 100. Die Tage werden von 1 bis 100 durchnummeriert, danach beginnt die Zählung wieder bei 1. Jeder Häftling führt eine Strichliste mit Feldern von 1 bis 100. Wenn am Tag i (i=1..100) der Häftling mit Nummer i (selbe Nummer!) in die Kammer geführt wird, dann schaltet er das Licht ein. Wenn ein Häftling mit anderer Nummer in die Kammer geführt wird, verläßt er den Raum mit ausgeschaltetem Licht. Wer in die Kammer geführt wird, prüft zuerst, ob sein Vorgänger das Licht eingeschaltet hatte. Ist das der Fall, kann er auf seiner Strichliste den Häftling mit der Nummer des Vortages abhaken.

Derjenige, dessen Liste zuerst voll ist, spricht die befreienden Worte.

Schneller geht es, wenn jeder auch dann das Licht anschaltet, wenn er weiß, dass der Kollege mit der Nummer von heute bereits im Raum war.

Achtung: Diese Strategie setzt voraus, dass die Häftlinge die einzelnen Tage unterscheiden können.

Der Nachteil ist, das diese Lösung unter Umständen sehr lange dauern könnte, nämlich  maximal 100!*100! = 2,3 * 10^313 Jahre (sprich 2,3 mit 313 Nullen hintendran). Das erste 100! damit alle 100 Sträflinge an genau 100 Tagen im Raum waren und das zweite 100! damit die Reihenfolge unter diesen 100 stimmt. Es kann sein dass sich die Dauer noch erhöht da ich nicht mit eingerechnet habe dass die Zählung exakt alle 100 Tage beginnen muss (z.B. kann so von Tag 50 bis 150 alle in der Zelle sein, davor/danach aber evtl. nicht).

Advertisement