hallo zusammen…habe mal eine frage zu einer interessanten aufgabe…
es soll die bruchfestigkeit von honiggläsern getestet werden.
es gibt ein regal mit n regalböden in höhe 1,2,…n.
Jedes Glas einer jeweiligen Sorte Honiggläser übersteht stets bis zu einer höhe x den fall ohne schaden, zerbricht jedoch beim fall aus höhe mindestens x+1. x ist die maximale fallhöhe diser glassorte.
um die maximal fallhöhe einer bestimmten sorte zu bestimmen, wenn wir nur ein glas zur verfügung haben, brauchen wir im schlimmsten fall n versuche, wir müssen von unten jeweils einen regalboden nach oben gehen.
wenn ein glas einmal kaputt ist, können wir es nicht mehr wiederverwenden zum testen. die sache sieht jedoch anders aus, wenn wir mehrere gläser derselben sorte zur verfügung haben.
jetzt soll ein vorgehen beschrieben werden, das mit 2 gläsern wenig versuche braucht, um exakt die max. fallhöhe zu bestimmen und es soll die anzahl der versuche f_2(n) im schlimmsten fall möglichst exakt sein. eine sublineare versuchzahl, also limes n->infinity (f_2(n))/n=0 ist möglich…
vielleicht hat jmd eine idee…
lg
Hallo!
Ich denke einfach mal drauf los. Meine Idee sieht so aus: Man setzt ein Honigglas auf das Regalbrett a. Überlebt es den Sturz, geht es bei 2a weiter und so fort. Geht es kaputt, dann braucht man höchstens noch (a-1) zusätzliche Versuche, um es rauszukriegen. Nun, wie wählt man a sinnvollerweise? Wählt man a zu klein, dann dauert die Testphase mit Glas 1 zu lang. Wählt man a zu groß, dann findet man sich zu schnell in der 2. Testphase wieder, die noch dazu erheblich länger dauert.
Die Anzahl der Regalbretter wird in (n/a) Gruppen geteilt. Der schlimmste Fall ist, wenn das Glas ganz oben erst zerbricht. Dann braucht man (n/a - 1) Testläufe mit dem ersten Glas und (a-1) Testläufe mit dem zweiten. Insgesamt also (n/a) + a - 2. Davon suchen wir ein Minimum. Also ableiten und Null setzen:
f’ = -n/a² + 1 = 0
a = Wurzel(n)
Wenn man die Maximalzahl der Versuche minimieren will, sollte man also eine Schrittweite von Wurzel(n) verwenden. Dann braucht man höchstens (2 Wurzel(n) - 2) Versuche.
Hier geht in der Tat f_2(n)/n gegen 0 wenn n gegen unendlich strebt. Ich weiß aber nicht, ob das die optimale Lösung ist. Man könnte ja die Schrittweise während des Versuchs mit dem ersten Honiglas auch ändern.
Ehrlicherweise muss ich auch zugeben, dass meine Lösung nicht völlig korrekt ist: hat man die unteren (n/a - 1) Gruppen dadurch eliminiert, dass auf dem Regalbrett (n - a) Glas 1 immer noch übersteht, so hat man für die verbleibenden a Bretter ja immer noch zwei Honiggläser zur Verfügung. Immerhin hat man so ein Honigglas gespart 
Michael