Dies ist die Lösung 4 von Aufgabe Gefangene und Glühbirne.
"Ein Zähler":
Bei der ersten Unterredung bestimmen die Häftlinge einen "Zähler". Alle anderen bemühen sich, vom Zähler genau einmal gezählt zu werden. Das geht folgendermaßen.
Wer selbst noch nie gezählt wurde und beim Betreten des Raumes die Glühbirne ausgeschaltet vorfindet, schaltet sie ein. Er kann sich damit als gezählt ansehen. Die Glühbirne bleibt eingeschaltet, bis nach einiger Zeit (zufällig) der "Zähler" wieder in die Kammer kommt. Er schaltet die Glühbirne aus und vermerkt für sich, dass ein Häftling, den er bisher noch nicht gezählt hatte, in der Kammer war.
Alle anderen lassen die Glühbirne unverändert.
Sobald der "Zähler" bis 99 gezählt hat, kann er verkünden, dass mit Sicherheit schon jeder einmal im Raum war.
Das Verfahren erfordert Geduld. Der Zähler muss mindestens 99 Mal das Zimmer aufsuchen. Da er im Mittel etwa alle 100 Tage ausgelost wird, dauert das etwa 100*99 Tage (etwas mehr als 27 Jahre).
In Wahrheit dauert es noch länger, weil - besonders in der Endphase - nicht notwendigerweise zwischen zwei Besuchen des "Zählers" ein verbliebener Ungezählter den Raum betreten hat.
Verbesserung 1:
Schneller geht es, wenn der "Zähler" nicht bei der Besprechung direkt bestimmt wird. Stattdessen kann man übereinkommen, dass derjenige, der am 2. Tag in die Kammer geführt wird, automatisch die Funktion "Zähler" übernimmt. Der Zähler betritt damit das Zimmer zum ersten Mal am 2. Tag anstatt sonst durchschnittlich am 50. Tag. Das erspart 48 Tage Wartezeit.
Verbesserung 2:
Noch schneller geht es, wenn die Funktion des Zählers demjenigen übertragen wird, der zuerst ein zweites Mal in die Kammer kommt.
Dazu wird der Glühbirne in den ersten 100 Tagen eine andere Bedeutung zugeordnet:
- Der Häftling von Tag 1 schaltet die Glühbirne ein. Er betrachtet sich als gezählt.
- Jeder weitere Häftling, der die Glühbirne eingeschaltet vorfindet, betrachtet sich ebenfalls als gezählt. Er lässt die Glühbirne unverändert.
- Sobald ein Häftling zum zweiten Mal in den Raum kommt, schaltet er die Glühbirne aus. Er weiß, dass er der Zähler ist und kennt die Anzahl der Häftlinge, die sich schon als gezählt betrachten können, an Hand der Tagesnummer.
- Jeder weitere Häftling, der bis zum Tag 100 den Raum betritt, lässt die Glühbirne unverändert.
- Wer in den ersten 100 Tagen die Glühbirne einmal in eingeschaltetem Zustand gesehen hat, gilt als gezählt.
Ab Tag 101 beginnt das "übliche" Verfahren, wo jeder noch nicht gezählte durch Einschalten der Glühbirne signalisiert, dass er gezählt werden möchte.
Im Durchschnitt kommt nach etwa 13 Tagen ein Häftling zum zweiten Mal in die Kammer. Der Rest der ersten 100 Tage vergeht zwar ungenutzt, der Zähler hat sich durch diesen Trick aber ca. 12 Zählungen, also 1200 Tage, erspart.
Verbesserung 3:
Anstatt einer Vorlaufperiode von 100 Tagen (siehe Verbesserung 2) könnte man davon auch mehrere machen.
Untersuchungen dazu wären hier noch zu ergänzen.