Ein weiteres Rätsel aus der Liste mit Interviewfragen für Mathematikerjobs vom letzten mal hat mir keine Ruhe gelassen, nämlich die

Aufgabe 2: Mit zwei identischen Kristallkugeln soll bei einem 100-stöckigen Hochhaus ermittelt werden, ab welchem Stock die Kristallkugeln kaputtgehen, wenn sie aus dieser Höher fallengelassen werden. Wieviele Messungen (d.h. Fallenlassen einer Kugel) muss man schlimmstenfalls durchführen, d.h. was ist die beste Strategie für die Messungen, gemessen am jeweils schlimmsten Fall (d.h. die maximale Anzahl, die bei einer Strategie benötigt werden)? Beide Kugeln dürfen kaputtgehen, aber die Antwort muss korrekt sein.

Ausnahmsweise ist die Antwort mal weder "binäre Suche" noch "Hashtabelle" (das sind die häufigsten Fragen bei Informatiker-Jobinterviews). Nachdem mir die Antwort nicht gleich eingefallen ist, habe ich auch hierfür ein Scheme-Programm geschrieben, welches durch "brute force" die beste Lösung ermitteln sollte. Dummerweise braucht das Programm aber zu lange, es läuft jetzt schon seit ein paar Stunden und hat noch keine Antwort ausgespuckt. Nachdem ich es an kleineren Fällen ausprobiert habe (z.b. 10-stöckiges Hochhause), ist mir aber doch noch eingefallen, wie ich die Aufgabe auf theoretischem Weg lösen kann (im nachhinein war es natürlich gar nicht so schwer...). Es folgt meine Lösung, wer es selbst probieren will, sollte also ab hier nicht weiterlesen.

Lösung: Ich beweise gleich Allgemein für n-stöckige Hochhäuser. Eine Strategie sei eine Folge von k Schritten s_1, s_2,...,s_k mit s_1 + s_2 + ... + s_k = n, so zu interpretieren, dass im ersten Schritt eine Kugel aus dem s_1-ten Stock geworfen wird. Zerbricht sie nicht, wird sie im zweiten Schritt aus dem s_1 + s_2-ten Stock geworfen, und so weiter. Sollte die erste Kugel zerbrechen, muss mit der zweiten Kugel sequentiell weitergetestet werden, da sonst das richtige Stockwerk nicht mit Sicherheit ermittelt werden könnte. Zerbricht die erste Kugel also im Schritt i, müssen mit der zweiten Kugel noch maximal s_i - 1 Tests durchgeführt werden, die Stockwerke s_1 + ... + s_(i-1) + 1 bist s_1 + ... + s_i - 1 müssen getestet werden.

Nun behaupte ich

I) Sei Max die maximal nötige Anzahl an Messungen. Dann gibt es eine optimale Strategie mit s_1 = Max.

Beweis: Zerbricht die erste Kugel im Stockwerk s_1 = Max, so sind noch maximal Max-1 Messungen mit der zweiten Kugel nötig, also maximal Max Messungen, falls die Kugel in s_1 zerbricht. Desweiteren sind für weniger Stockwerke auf keinen Fall mehr Messungen nötig, d.h. das Vergrössern von s_1 kann den "schlimmsten Fall" für die restlichen Messungen nicht verschlechtern, da ja weniger zu testende Stockwerke übrigbleiben (könnte man mathematisch exakter Formulieren, aber das hier ist ja nur ein Blog).

Ausserdem gilt

II) Es gibt eine optimale Strategie s_1,...,s_k mit s_1 = Max und s_(i+1) = s_i +1 für i < k und s_k < s_(k-1).

Beweis: nach I) können wir von s_1 = Max ausgehen. Daher ist s_2 < s_1. Analog zum Beweise von I) folgt, dass s_2 auf Max-1 erhöht werden kann, und so weiter für s_3,...,s_(k-1). s_k muss als Sonderfall nur so gross sein, wie Stockwerke nach den vorherigen Schritten übrig sind. (Wieder Erspare ich mir im Sinne der Kürze die exakte mathematische Formulierung).

Aus I) und II) folgt, dass es eine optimale Strategie der Form Max, Max-1, ..., Max-k-2, s_k gibt mit s_k < Max-k-2. Nun ist ja 1 + 2 +...+Max eine arithmetische Folge mit Wert Max*(Max+1)/2. Die Gleichung Max*(Max+1)/2 = n lässt sich lösen (quadratische Gleichung Max²+Max-2n = 0). Für n = 100 ist die Lösung Max = 13,65..., da Max eine ganze Zahl sein muss ergibt sich als optimale Strategie 14,13,12,11,10,9,8,7,6,5,4,1, mit der maximal 14 Messungen benötigt werden.

Praktische Anwendungen sind mir nicht bekannt...