Rekursionsgleichung für die maximale Etagenzahlh(v,k) bezeichne die Anzahl der Etagen, die man mit v Versuchen und k Eiern testen kann. Offenbar gilt für k > v die Gleichung h(v,k)=h(v,v), da ja bei v Versuch höchstens v Eier kaputt gehen. Wenn man nichts testen kann, also v=0 oder k=0, dann ist h(0,k)=0 bzw. h(v,0)=0. Betrachtet man nun einen Fallversuch aus Etage Nummer n bei dem noch v Versuche und k Eier zur Verfügung stehen. Zerspringt das Ei bei diesem Versuch, dann hat man danach noch v-1 Versuche und noch k-1 Eier und man muss damit die Etage unter der n-ten finden, ab der die Eier platzen. Also sollte n = h(v-1,k-1)+1 gewählt werden. Übersteht das Ei den Fallversuch, dann kann man danach noch h(v-1,k) Etagen über der n-ten Etage testen. D.h. h(v,k)=h(v-1,k-1)+1+h(v-1,k).
Differenz der maximalen Etagenzahl zum Optimum für eine spezielle Zahl von FallversuchenWenn v Fallversuche erlaubt sind, erhält man maximal v Ja/Nein Ergebnisse. D.h. maximal 2^v Möglichkeiten zwischen denen entschieden werden kann. Da es bereits eine Möglichkeit ist, wenn die Eier aus allen überprüfbaren Etagen ohne Schaden fallen können, verbleiben maximal n(v)=2^v-1 Etagen, die mit v Fallversuchen getestet werden können.
Es sei nun g die Anzahl an Versuchen, die man mehr hat als Kugeln, also g=v-k und v=g+k. Betrachtet man nun die Differenz
d(g,k)=n(k+g)-h(k+g,k) für g>=0 und
d(g,k)=d(0,k+g) für g < 0 (mehr Eier als Versuche)
und setzt für g>=0 obige Rekursionsgleichung ein:
d(g,k)=n(k+g)-(h(k+g-1,k-1)+1+h(k+g-1,k))
und nun zurück mit h(v,k)=n(v)-d(v-k,k)
d(g,k)=n(k+g)-(n(k+g-1)-d(g,k-1)+1+n(k+g-1)-d(g-1,k))
=n(k+g)-2n(g+k-1)-1+d(g,k-1)+d(g-1,k)=d(g,k-1)+d(g-1,k)
Für g>=0 ist d(g,0)=n(g)-h(g,0)=n(g) ein Startwert zur Berechnung weiterer d(g,k).
Damit hat man eine Rekursionsvorschrift für die Differenzen:
d(g,k)=d(g,k-1)+d(g-1,k) und d(g,0)=2^g-1 |
die man beginnend mit g=0 dann g=1 usw. in Formeln die nur noch von k abhängen auflösen kann.
Fall g=0 (Alphacene)d(0,0) = n(0)=2^0-1=1-1=0.
d(0,k)=d(0,k-1)+d(-1,k) = d(0,k-1)+d(0,k-1) = 2 d(0,k-1) = 0. Das heißt, dass Alphacene auch immer alle 2^v Entscheidungsmöglichkeiten auf 2^v-1 Etagen umsetzt.
Fall g=1 (Alphanane)d(1,0)=n(1)=2^1-1=2-1=1
d(1,k)=d(1,k-1)+d(0,k)=d(1,k-1)=1
Fall g=2d(2,0)=n(2)=2²-1=3
d(2,k)=d(2,k-1)+d(1,k)=d(1,k-1)+1=3+k
Fall g=3 (Alphabene)d(3,0)=n(3)=2³-1=7
d(3,k)=d(3,k-1)+d(2,k)=d(3,k-1)+3+k=7+3k+(1+2+3+...+k)=7+3k+(k(k+1))/2=k²/2+7k/2+7
Hier wurde die bekannte Summenformel für natürliche Zahlen aus der Erzählung über den Schüler C.F. Gauß verwendet.
Spezieller Fall für die drei AlphaninnenIm Rätsel sollte h(A+1,A)+h(B+3,B)=h(C,C) sein. Also
(2^(A+1)-1)-1 + (2^(B+3)-1)-(B²/2+7B/2+7)=2^C-1 und umgestellt steht da:
2^(B+3)+2^(A+1)=2^C+(B²/2+7B/2+9).
Stellt man sich die letzte Gleichung in Binärschreibweise vor und geht von B>=1 aus, dann kann man erkennen, dass B+3=C und 2^(A+1)=B²/2+7B/2+9 sein muss. Die Fälle B=1 und B=2 untersucht man im Detail. Bei B=2 gäbe es eine Lösung mit A=0 und C=3, die aber ausgeschlossen wird, da Alphanane ohne Eier ja gar keine Versuche machen kann. Für B>=3 sieht man sofort, dass C=B+3 sein muss.
Also muss gelten: B²+7B+18-2^(A+2)=0. Diese Gleichung hat für B>0 die Lösung
B=-7/2+Wurzel(49/4-18+2^(A+2))=(Wurzel(2^(A+4)-23)-7)/2.
Wurzel(2^(A+4)-23) muss also größer gleich 9 sein und 2^(A+4)-23 eine Quadratzahl größer gleich 81. D.h. A+4 muss größer gleich 7 sein. Da ab A>=4 für gerade A der Abstand der Quadratzahl 2^(A+4) zur vorhergehenden Quadratzahl größer als 23 ist, kommen nur ungerade A>=3 als Lösung in Frage. Testet man:
A 2^(A+4) 2^(A+4)-23
3 128 105 keine Quadratzahl
5 512 489 keine Quadratzahl
7 2048 2025 = 45²
Mit A=7 ist B=(45-7)/2=19 und C=B+3=22 die gesuchte Lösung.
