Während die Froscon Besucher bei dem Voc am Rhein neue Rundenrekorde aufstellen konnten, war auch für das geistige Wohl gesorgt. Wer das Eierrätsel richtig löste, hat attraktive Gutscheine von Amazon und ThinkGeek gewonnen.
Das Froscon 2011 Eier Rätsel
Gegeben seien Eier mit einer unbekannten, aber für alle Eier gleichen Stabilität N. In dem Sinne: sie überstehen einen Fall aus dem N-ten Stockwerk, aber nicht mehr aus dem N+1-ten Stockwerk. Dabei ist N minimal 0 und maximal 100.
Die Stabilität soll jetzt bestimmt werden, indem wir von einem Hochhaus mit hinreichend vielen Etagen Eier herunterfallen lassen. Uns interessieren optimale Verfahren, bei denen die Anzahl der Versuche, die man im worst case – für das ungünstigste N – machen muss, möglichst klein ist.
Wenn man nur ein Ei zur Verfügung hat, so ist das beste (gewissermaßen das einzige) Verfahren die lineare Suche, bei der man mit der ersten Etage anfängt und sich dann Etage für Etage hocharbeitet. Wenn das Ei beim Fall aus der m-ten Etage kaputt geht, so weiß man, dass N = m-1 ist. Im worst case muss man also 100 Versuche machen (wenn N = 100 ist).
Wenn man beliebig viele Eier zur Verfügung hat, so ist das beste Verfahren die binäre Suche. Im worst case
muss man also 7 Versuche machen.
Was ist aber die Anzahl der Versuche, die man bei einem optimalen Verfahren im worst case machen muss, wenn
man zwei Eier zur Verfügung hat? Und bei drei Eiern?
Ei des Kolumbus oder des Rätsels Lösung
Vorüberlegungen
Angenommen man hat zwei Eier zur Verfügung. Folgt man der Idee der binären Suche und lässt das erste Ei in der 50. Etage fallen und es geht kaputt, so weiß man, dass N minimal 0 und maximal 49 ist. Man hat einen Versuch durchgeführt, aber leider nur noch ein Ei zur Verfügung. Das heißt, um heraus zu finden was die Stabilität ist, kann man nur linear vorgehen und braucht im schlimmsten Fall (N = 50) jetzt nochmal 49 Versuche. Insgesamt
also 50 Versuche.
Geht es besser? Lässt man das erste Ei aus dem 10. Stock fallen und es geht kaputt, so muss man jetzt die Stockwerke 1 bis 9 linear durchprobieren. Insgesamt im schlimmsten Fall also 10 Versuche. Geht das Ei jedoch nicht kaputt, so hat man einen Versuch verbraucht, aber noch beide Eier. Startet man den nächsten Versuch im 20. Stock und das Ei geht kaputt, so hat man jetzt zwei Versuche verbraucht, nur noch ein Ei übrig und man weiß, dass N zwischen 10 und 19 liegt. Man braucht aber jetzt noch 9 weitere Versuche. Insgesamt also 11 Versuche.
Geht man bei zweiten Versucht statt in den 20. Stock nur in den 19. Stock und das Ei geht kaputt, so kann man in 10 Versuchen feststellen, was die Stabilität ist. Das heißt, geht man im ersten Schritt in den m. Stock, um nächsten Schritt in den (m-1). Stock, usw. kommt mit m Versuchen aus. Allerdings muss m so groß sein, dass die Summe
m + (m-1) + (m-2) + … + 1 = m * (m + 1) /2
größer als 99 ist. Für m = 10 ist die Summe allerdings nur 55. Für m = 14 ist die Summe gleich 105. Das heißt, mit diesem Verfahren braucht man im schlimmsten Fall 14 Versuche, kommt aber mit zwei Eiern aus. Die Frage ist jetzt, gibt es vielleicht einen ganzen anderen Algorithmus, welcher noch viel besser ist. Die binäre Suche kommt ja schließlich auch mit 7 Versuchen aus.
2 Eier Theorie
Dazu müssen wir etwas Theorie anwenden.
N(i,m)
bezeichne die maximale Stabilität, welche man erraten kann, wenn man i Eier und m Versuche aufwendet. Dann gilt für i = 1
N(1,m) = 1 + N(1,m – 1)
Lässt man das Ei aus dem 1 Stock fallen, und es geht kaputt, so ist die Stabilität 0. Also muss
N(1,1) = 1
sein. Die Rekursion kann man jetzt auflösen und erhält:
N(1,m) = m
Wie sieht es bei zwei Eiern aus?
Lässt man das erste Ei aus dem x.ten Stock fallen, dann gibt es zwei Möglichkeiten:
(a) Das Ei geht kaputt. In diesem Fall muss man die Ein-Eier-Strategie für 0 … x-1 anwenden.
(b) Das Ei geht nicht kaputt. In diesem Fall kann man die Zwei-Eier-Strategie für x+1 .. N anwenden.
Das heißt, es gilt
N(2,m) = (N(1,m-1) + 1) + N(2,m-1)
Wir wissen bereits, dass
N(1,m-1) = m-1
gelten muss. Also
N(2,m) = m + N(2,m-1)
trägt man dies als Tabelle auf, so gilt:
m N(2,m)
1 1
2 3 = 2 + 1
3 6 = 3 + 3
4 10 = 4 + 6
5 15 = 5 + 10
6 21 = 6 + 15
7 28 = 7 + 21
8 36 = 8 + 28
9 45 = 9 + 36
10 55 = 10 + 45
11 66 = 11 + 55
12 78 = 12 + 66
13 91 = 13 + 78
14 105 = 14 + 91
Das heißt, das erste Mal, wenn N(2,m) größer oder gleich 100 ist, tritt bei m gleich 14 auf. Unsere oben beschriebene Algorithmus ist also ideal. Mit weniger als 14 Versuchen geht es nicht.
3 Eier Theorie
Bei 3 Eiern ist die Argumentation die gleiche
N(3,m) = (N(2,m-1) + 1) + N(3,m-1)
tragen wir dies wieder als Tabelle auf, so sieht man
m N(2,m) N(3,m)
1 1 1
2 3 = 2 + 1 3 = (1 + 1) + 1
3 6 = 3 + 3 7 = (3 + 1) + 3
4 10 = 4 + 6 14 = (6 + 1) + 7
5 15 = 5 + 10 25 = (10 + 1) + 14
6 21 = 6 + 15 41 = (15 + 1) + 25
7 28 = 7 + 21 63 = (21 + 1) + 41
8 36 = 8 + 28 92 = (28 + 1) + 63
9 45 = 9 + 36 129 = (36 + 1) + 36
Also ist das kleinste m, so dass N(3,m) größer oder gleich 100 ist, gleich 9. Damit ergibt als
Algorithmus:
Gehe in den 36 Stock und das erste Ei fallen. Geht es kaputt, haben wir noch zwei Eier und müssen die Stockwerke 1 .. 36 ausprobieren. Aus dem Überlegung zu N(2,m) wissen wir, dass man 8 Versuch braucht. Das heißt, insgesamt brauchen wir 9 Versuche.
Geht das erste Ei nicht kaputt, so lassen wir das erste Ei aus dem 36 + 28 Stock fallen. Geht es kaputt, haben wir zwei Versuche gebraucht und noch zwei Eier. Um die Stockwerke 37 .. 64 auszuprobieren, brauchen wir jetzt 7 Versuche. Insgesamt also wieder 9.
Und so weiter.
Geschlossene Form
Man dann die Werte für N(2,m) und N(3,m) per Programm berechnen oder sich eine geschlossene Form überlegen. Wir wissen bereits
N(1,m) = m
N(2,m) = m + N(2,m-1)
Folgt man z. B. http://classes.soe.ucsc.edu/cmps201/Winter00/handouts/recur.pdf so kann man die Rekursion auflösen und erhält
N(2,m) = m * (m + 1) / 2
Für drei Eier folgt damit
N(3,m) = (N(2,m-1) + 1) + N(3,m-1)
bzw. mit obigen Wissen
N(3,m) = (m*m – m + 2) / 2 + N(3,m-1)
Löst man die Rekursion auf erhält man
N(3,m) = m * (m*m + 5) / 6
Wer wissen möchte, wie man solche geschlossene Formeln systematisch bestimmen kann, dem sei das Buch “Concrete Mathematics” von Ronald L. Graham, Donald E. Knuth (genau der von TAOCP) und Oren Patashnik empfohlen.
Der gute Eindruck hat sich bestätigt und wir sind froh, dass wir dabei waren. In über 40 Vorträgen, Workshops und Diskussionsrunden konnten sich Web-Entwickler über aktuelle Technologien und Trends informieren. Die Bandbreite der Themen war sehr groß. So gab es technische Themen (z.B. Many-Cores & Functional Programming von Prof. Dr. Friedrich Esser), aber auch praktische Leitfäden zu Randthemen (z.B. Gut verhandeln von Judith Andresen).
Auf unserem “World of VOC”-Messestand präsentierten wir die Produkte SimpleVOC (schneller Key-Value-Store) sowie den SessionVOC. Hier möchten wir noch einmal ausdrücklich erwähnen: Der SimpleVOC und SessionVOC sind als Open-Source-Versionen verfügbar und können selbstverständlich für eigene Projekte verwendet werden! Die Funktionen sind dabei nicht extrem reduziert, wie einige Besucher unseres Stands vermutet hatten.