| Autor |
Beitrag |
    
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 03. August, 2002 - 19:15: | 
|
Es gibt eine kritische Höhe h (in unserem Fall die Nummer eines Stockwerks) für die Bruchfestigkeit von Sicherheitsbehältern. Diese Behälter überstehen (auch mehrere) Stürze aus einem Stockwerk <= h völlig unversehrt. Wirft man sie aber aus einem höheren Stock (also ab Nr. h+1) zerbrechen sie beim Aufprall.
Wie kann man diese kritische Höhe h mit möglichst wenigen Versuchen exakt ermitteln, wenn man zwei Behälter zur Verfügung hat und für h alle Stockwerke von 1 bis n in Frage kommen?
Nehmen wir als konkretes Beispiel (zum Vergleichen der "Formeln") die Frankfurter Commerzbank: Wieviele Versuche braucht man für n=62 Stockwerke ?
|
Thomas (johnnie_walker)
Mitglied
Benutzername: johnnie_walker
Nummer des Beitrags: 23
Registriert: 06-2002
| | Veröffentlicht am Samstag, den 03. August, 2002 - 19:31: |
|
Hi sol@ti,
scheint ja sehr einfach zu sein, wenn das mal nicht nach Glatteis aussieht...
unterstes Stockwerk = 0
Da man h exakt ermitteln muß, darf nur ein Behälter zu Bruch gehen, also mit Stockwerk eins beginnen und jeweils um 2 nach oben, wenn der Behälter es übersteht. Zerbricht er, wirft man den zweiten aus dem Stockwerk eins darunter und egal ob er zerbricht oder nicht, hat man h exakt bestimmt.
Eine andere Lösung sehe ich nicht, da man nur zwei Behälter zur Verfügung hat.
Die Lösung für n=62 hängt doch von h ab, kann man die denn allgemein bestimmen ?
Also, wo ist mein Denkfehler ?
Gruß
Thomas |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 03. August, 2002 - 20:14: |
|
Hallo Thomas,
ich meinte: Wieviele Versuche braucht man bei n=62 Stockwerken im schlechtesten Fall. Also nach wievielen Versuchen ist man (für festes n) garantiert fertig.
Bei deiner Strategie müssten das 31 Versuche sein (wenn h=61). Die Formel für deine Strategie ist also (im wesentlichen) n/2.
Viele Grüße
sol@ti
|
Thomas (johnnie_walker)
Mitglied
Benutzername: johnnie_walker
Nummer des Beitrags: 25
Registriert: 06-2002
| | Veröffentlicht am Samstag, den 03. August, 2002 - 23:55: |
|
Hi sol@ti,
nehme alles zurück, müsste auch so gehen :
Beginne mit Stock 3, dann 1 wenn Crash, 6 wenn noch unbeschädigt usw.
In schlechtesten Fall gäbe es dann 20 Versuche bis Stockwerk 60 zuzügl. des letzten Versuchs bei Stockwerk 62 = 21 Versuche.
Als Formel heißt das wahrscheinlich [n/3] + 1, wobei [] kleinster ganzzahliger Vorgänger heißen soll.
Gruß
Thomas |
Thomas (johnnie_walker)
Mitglied
Benutzername: johnnie_walker
Nummer des Beitrags: 26
Registriert: 06-2002
| | Veröffentlicht am Sonntag, den 04. August, 2002 - 00:18: |
|
Formel ist natürlich Quatsch, ich kann halt nicht mit eurem mod umgehen, vielleicht so was wie
n/3+[(n mod 3)] mit []= erhält für (n mod 3 = 2) und (n mod 3 = 1) den Wert 1, für (n mod 3 = 0) den Wert 0. Hoffe ich mache mich verständlich.
Thomas |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1278
Registriert: 07-2000
| | Veröffentlicht am Sonntag, den 04. August, 2002 - 11:39: |
|
Versuche Stockwerke
11, 21, 30, 38, 45, 51, 56, 60
mit dem ersten Behälter, bis er zerbricht. Wenn er z. B. den Sturz aus dem 45. Stock nicht aushält, dann
39, 40, 41, 42, 43, 44
mit dem zweiten Behälter. Wenn ich mich nicht irre, kommt man schlimmstenfalls mit 11 Stürzen aus. Weiß aber nicht, ob das optimal ist.
Z. |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Sonntag, den 04. August, 2002 - 17:11: |
|
Bravo Zaph,
"höchstens 11 Versuche" ist das Minimum für 62 Stockwerke. Es gibt auch andere Strategien mit 11 Versuchen, aber deine Lösung hat den großen Vorteil, dass man sie verallgemeinern und damit eine Formel herleiten kann:
Bei n Stockwerken sind höchstens ]√(2n)-1/2[ Versuche notwendig. ( ][ = Aufrunden )
"Von drauß', vom Walde kommt sie her ...", nein - sicher nicht! Wo kommt die Formel wirklich her?
Bin gespannt auf einen schönen Beweis!
sol@ti
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1282
Registriert: 07-2000
| | Veröffentlicht am Sonntag, den 04. August, 2002 - 18:06: |
|
Hi Sol@ti, kann mir ungefähr vorstellen, wie ein Beweis aussieht, dass man immer mit ]-1/2 + Wurzel(2n)[ Versuchen hinkommt.
Aber, wieso es nicht besser gehen soll ... ??? |
Jan Martin Krämer (species5672)
Mitglied
Benutzername: species5672
Nummer des Beitrags: 44
Registriert: 07-2002
| | Veröffentlicht am Sonntag, den 04. August, 2002 - 18:28: |
|
Wenn höchstens 11 das Minimum für 62 Stockwerke sind, wo ist der Fehler bei meiner Strategie:
Man setzt sich 2 Variablen:
a= kleinstes Stockwerk bei dem es zerbricht
b= größtes Stockwerk bei dem es nicht zerbricht
Am Anfang ist natürlich a=62 (ich nehme mal an es zerbricht dort, ansonsten ändert sich ja nicht viel, hat man halt 1 Versuch mehr eventuell) und b=0.
Man testet jetzt jeweils das Stockwerk mit der Nummer (a-b)/2 (notfalls runden). Je nachdem wird dann a oder b angepasst.
Ich komme auf 6 Versuche im ungünstigsten Fall
Erläuterung (ohne Beweis):
Betrachten wir ein Haus mit 64 Etagen (das macht die Anzahl der Versuche ja höchstens höher).
1. Versuch (a-b)/2=32
Je nachdem ob er zerbricht oder nicht, müssen wir ja nur noch 32 Etagen testen, entweder zerbricht er, dann ist die kritische Höhe zwischen dem 0. und dem 32. Stockwerk oder er zerbricht nicht, dann ist die kritische Höhe zwischen dem 32. und dem 64. Stockwerk.
Es ist einleuchtend das bei beiden Fällen gleich viele Versuche notwendig sind, ich beschränke mich darauf anzunehmen das der Behälter jedesmal zerbricht.
Also ist jetzt a=0 und b=32
2. Versuch Nächster Versuch wäre demnach bei 16
Wir haben die Möglichkeiten für die kritische Höhe auf 16 Stockwerke eingegrenzt, 0 bis 16 und 16 bis 32.
Beim 3. Versuch hätte man nur noch 8 Stockwerke zu untersuchen, beim 4. 4, beim 5. 2, beim 6 hat man es dann entweder getroffen, oder weiß das es das andere war.
Falls es genau 2,4,8,...,32 ist, findet man es dementsprechen früher.
Wie man sieht, ist die Anzahl der Versuch die man für ein Haus mit n Etagen braucht gleich dem kleinstmöglichen k, so dass 2^k³n.
Ich sehe keinen Fehler bei mir, irgendwelche Kritik oder ist 6 die Lösung?
(Beitrag nachträglich am 04., August. 2002 von species5672 editiert) |
SpockGeiger (spockgeiger)
Senior Mitglied
Benutzername: spockgeiger
Nummer des Beitrags: 551
Registriert: 05-2000
| | Veröffentlicht am Sonntag, den 04. August, 2002 - 18:45: |
|
Hi Jan
Dein Ansatz ist die Binärsuche, sie funktioniert hier aber nicht, weil Du nur zwei Tonnen zur Verfügung hast. Was passiert, wenn bei den ersten beiden Versuchen die Tonne bricht?
viele Grüße
SpockGeiger
(Beitrag nachträglich am 04., August. 2002 von SpockGeiger editiert) |
Jan Martin Krämer (species5672)
Mitglied
Benutzername: species5672
Nummer des Beitrags: 45
Registriert: 07-2002
| | Veröffentlicht am Sonntag, den 04. August, 2002 - 19:56: |
|
MAL WIEDER nicht genau genug die Aufgabenstellung gelesen.
Ich bin so ein depp, ich glaub ich lerns nie |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Montag, den 05. August, 2002 - 16:59: |
|
Hallo Zaph,
ich verwende folgende Bezeichnungen:
1 <= s1 < s2 < ... < sp <= n sind die Nummern der Stockwerke aus denen der 1.Behälter versuchsweise geworfen wird. Man beginnt mit s1 und wirft immer aus dem nächsten sk, bis der 1. Behälter zerbricht. Dann müssen mit dem 2.Behälter alle Stockwerke seit dem letzten Wurf einzeln durchprobieren werden.
vk ist die Anzahl der tatsächlich benötigten Versuche, wenn der 1.Behälter beim Wurf aus sk zerbricht (k=1,...,p) und vp+1 die Anzahl der benötigten Versuche, wenn der 1.Behälter auch den Wurf aus sp übersteht.
w ist die Anzahl der schlechtestenfalls benötigten Versuche (w soll minimiert werden).
Dann ist w = max(vk), k=1,...,p+1 und es gilt: vk <= w
Es ist
v1 = s1
vk = sk - sk-1 + (k-1) , für k=2,...,p
vp+1 = n - sp + p
Daraus ergeben sich die Abschätzungen:
s1 <= w
s2 <= s1 + w - 1 <= 2w - 1
s3 <= s2 + w - 2 <= 3w - 3
...
sk <= sk-1 + w - (k-1) <= k*w - (1+2+...+(k-1)) = k*w - (k-1)*k/2
...
sp <= p*w - (p-1)*p/2
und
n - sp + p <= w , also: n + p - w <= sp
Daher: n + p - w <= p*w - (p-1)*p/2, also: w >= n/(p+1) + p/2
Die Funktion y(x) = n/(x+1) + x/2 hat ihr Minimum bei x0 = √(2n) - 1
Das (für diese Abschätzung) optimale ganzzahlige p ist also [x0] oder ]x0[
Für n=62 ist x0 ~ 10.136
p=10 ==> w > 10.636
p=11 ==> w > 10.666
Daher gibt es keine Möglichkeit mit (schlechtestenfalls) weniger als 11 Versuchen h zu bestimmen.
@Jan: Sehr gut, du hast die optimale Strategie wenn die Einschränkung auf 2 Behälter wegfällt.
viele Grüße
sol@ti
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1284
Registriert: 07-2000
| | Veröffentlicht am Montag, den 05. August, 2002 - 21:55: |
|
Äußerst clever, Sol@ti, aber gestatte mir einige Rückfragen.
Wieso kann
1 <= s1 < ... < sp <= n
vorausgesetzt werden?
Wieso gilt
vp+1 = n - sp + p?
Wir haben hier doch noch ZWEI intakte Behälter!
(BTW, muss es nicht
v1 <= s1
vk <= sk - sk-1 für k=2,...,p
vp+1 <= n - sp + p
heißen?)
Sind immer ziemlich eklig, solche Beweise, wie ich finde...
Gruß
Z. |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 16:19: |
|
Hallo Zaph,
vielen Dank für dein Interesse. Ich zeig's am besten an deiner Strategie:
1.) 1 <= s1 < ... < sp <= n heißt ja nur, dass der 1.Behälter aus p verschiedenen Stockwerken geworfen wird. p ist frei wählbar.
Bei dir: 1 <= 11 < 21 < 30 < 38 < 45 < 51 < 56 < 60 <= 62. Du hast p=8 gewählt.
Oder meinst du, warum man nicht gemischt wirft: erst vom 45., dann vom 11., usw. ?
Stell dir vor der 1.Behälter bricht dann gleich beim ersten Wurf aus dem 45. - was dann ? 44 weitere Einzelversuche! Und dieses Risiko hätte man jedesmal, wenn die sk nicht der Reihe nach durchprobiert werden.
2.) vp+1 ist die tatsächliche Anzahl der Versuche (im schlechtesten Fall), wenn der 1.Behälter vorher schon p Würfe überstanden hat.
Bei dir: 8 Würfe unversehrt (aus 11.,21.,...,60.Stock) ==> Wurf aus 61. und 62.Stock.
Also v9 = 62 - 60 (2 Versuche von s8 bis n) + 8 (die bereits überstandenen)
Allgemein: vp+1 = n - sp + p
3.) Betrachten wir deine Strategie unter der Annahme, dass der 1.Behälter genau beim Wurf aus dem 45.Stock zerbricht, also v5. Dann wurde der 1.Behälter 5 Mal geworfen und jetzt muss der 2.Behälter aus den Stockwerken 39,40,41,42,43 und schlimmstenfalls noch 44 geworfen werden.
Also v5 = 45 - 38 - 1 (Würfe mit 2.Behälter) + 5 (Würfe mit 1.Behälter)
Allgemein: vk = sk - sk-1 - 1 + k
viele Grüße
sol@ti
|
|
