Ein kleines Rätsel…
Zur Abwechslung mal was zum Nachdenken. Wer die beste Lösung am schnellsten präsentiert, landet ganz oben auf der Postkartenliste (nicht dass ich im Moment welche schreiben würde, aber sobald der Road Trip losgeht wohl spätestens…)
Nehmen wir an, wir haben 2 Eier und ein hundertstöckiges Hochhaus. Ferner geht die Eier ab einer bestimmten Hochhaushöhe X kaputt, davor bleiben sie ganz (z.B. bei X=20 würde das Ei bei einem Wurf aus dem 20. Stock kaputt gehen, aus dem 19. aber ganz bleiben).
Die Frage: Wie bestimmt man X am schnellsten und wie schnell ist am schnellsten?
Update: Was denn, nur 3 Tipps? Ich dachte, meine Zielgruppe wären Informatiker ! Oder ist euch die Aufgabe zu trivial und ihr denkt, 18 ist das Optimum? Mal als Anregung…meine momentane Lösung liegt bei 14, jemand ne Idee wie?
Am 28. November 2007 um 10:35 Uhr
Realitätsnah: Wir werfen ein Ei aus dem erstem Stock. Es ist kaputt. die Lösung ist “0″. O(1).
Abstrakt: Das erste Ei aus dem X. Stock. Bleibt es ganz, werfen wir das gleiche Ei aus dem 2X.Stock usw., immer X Stockwerke hinzuaddieren.
Geht es kaputt fangen wir mit dem verbleibendem Ei beim letztem Stock an, wo es noch ganz blieb. Also falls das erste beim X. kaputt ging, fangen wir bei 1 an, falls es im 2X. kaputt geht fangen wir beim X+1. an. usw. O(n/X + X)) (n/x fürs erste Ei, X fürs zweite Ei). Nun noch X so wählen, dass 100/X+X minimal ist.
Am 28. November 2007 um 11:09 Uhr
Na, das geht ja wohl auch logarithmisch, oder?
Setze Startsuchintervall auf [1:100], teste Eierwurf aus dem Mittel des Intervalls, also Stockwerk 50. Wenn es kaputt geht, setze Intervall auf [1:49], sonst auf [51,100] und iteriere. In O(log_2 n).
Am 28. November 2007 um 11:10 Uhr
Ach soo, wir haben nur ZWEI Eier!
Am 28. November 2007 um 11:15 Uhr
Hmm, wenn ich dir jetzt helfe, unterstütze ich google bei ihren Weltherrschaftsplänen?
Egal:
das gesuchte Optimum von floh oben ist b=floor(sqrt(h)), wenn h die Höhe des Hauses angibt. Bei abzählbar undendlich vielen Stockwerken wähle b beliebig. Bei überabzählbar viel Stockwerken nimm die Eier und bewirf damit den Architekten.
Wirf nun Ei 1 nacheinander aus Stock b, 2b, 3b etc.. bis es bei i*b kaputtgeht. Starte nun mit Ei 2 in ((i-1)*b)+1, dann ((i-1)*b)+2 etc… bis du das richtige Stockwerk ermittelt hast.
Damit komme ich bei Gleichverteilung der Stockwerke auf sqrt(h)+sqrt(h)-1 als worst case (hmm, Wurst-Käse mit Ei… ich hab Hunger!) und 0.5*(sqrt(h)+sqrt(h)-1) als average case.
Disclaimer: Diese Aussage entstand vor der ersten Tasse Kaffee. Ich übernehme keine Garantie für Korrektheit, Zuverlässlichkeit und ähnliche gewünschte Eigenschaften.
Am 28. November 2007 um 11:19 Uhr
Oh, ich sehe grade dass die Höhe gegeben ist…
Damit komme ich bei meiner Lösung auf max. 19 Würfe (Die Zahl der Treppenstufen zu berechnen überlasse ich anderen…), im Median 10 Würfe.
Beat this!
Am 28. November 2007 um 13:46 Uhr
18 Würfe reichen, da wir laut Aufgabenstellung wissen, dass die Eier auf jeden Fall kaputt gehen. Man wirft das erste Ei bei 10, 20, …, 90; falls das bis dahin nicht kaputt geht, probiert man 91 bis 99 aus. Überlebt es diese 18 Würfe, muss X=100 gelten. Geht es vorher kaputt, braucht man maximal 9 Würfe mit dem zweiten Ei, um die Einerstelle zu bestimmen, die 0 fällt raus, da diese Stellen mit der ersten Reihe geprüft wurden.
Am 29. November 2007 um 16:10 Uhr
Naja, man kann die Testintervalle entsprechend der bereits durchgeführten Würfe skalieren. z.B: 15,15+14=29,15+14+13= 42,15+14+13+12=54,65,75,84,92,99 Sollte im worst-case
Am 29. November 2007 um 16:11 Uhr
*huch* verschluckt der die Hälfte der Antwort.: …sollte im worst-case 15 Würfe ergeben, falls ich mich nicht verzählt habe. Mit angemessenem Intervall-Anpassen kommt man dann vermutlich auf die 14
Am 29. November 2007 um 19:14 Uhr
Bei dem Rätsel fiel mir spontan die Physikprüfung von Niels Bohr ein. Die meisten werden mittlerweile schon davon gehört haben, aber wer es noch kennt, schaut doch bitte mal hier (bissl runterscrollen, Überschrift ist fettgedruckt):
http://chemie.fh-friedberg.de/htmltext/mathematikerwitze.htm
Am 29. November 2007 um 19:26 Uhr
Da hat Harry recht, mit 14, 27, 39… kommt man auf die 14 (wenn X=0 ausgeschlossen wird), ansonsten klappt es mit 13, 26, 38… Aber wenn Du schon so eine Aufgabe stellst, dann kannst Du sicher beweisen, dass 14 optimal ist, oder?
Ich schick Dir dann auch eine Postkarte aus Frankfurt.
Schade übrigens, dass hier keiner mal schnell ein Programm geschrieben hat, um das einfach auszurechnen.
Am 29. November 2007 um 19:27 Uhr
+nicht
Am 1. Dezember 2007 um 03:55 Uhr
1. Die maximale Zahl der Stockwerke ist M=100
2.Die laufende Nummer der Stockwerke ist S, von 1 bis M
3. Das Stockwerk, bei dem ein Ei zu Bruch geht, ist X, von 1 bis M
4. Wichtig ist nun die Wahl des Stockwerks D für den 1. Versuch mit dem 1. Ei. Zerbricht es, so muß man mit dem 2. Ei nacheinander die Stockwerke S=1, S=2 … testen. Bricht das 2. Ei bei S=3, so hat man dafür 1+3=4 Versuche benötigt. Zerplatzt das 2. Ei bei X=D-1, so hat man D Versuche benötigt, zerplatzt es nicht hat man ebenfalls D Versuche benötigt.
5. Ist X>D, zerplatzt das 1.Ei beim 1. Versuch nicht, so macht man einen 2.Versuch z.B. bei S=2*D, S=3*D…
6. Aus der Addition der Versuchefür alle X von 1 bis M ergibt sich der Wert A. Je kleiner A, desto schneller ist man fertig.
7. Das Minimum A=1019 ergibt sich mit D=14 und dem 2. Versuch bei 2*D-1=27, 3. Versuch bei 3*D-1-2=39 etc. Da M=100 nicht ohne Rest durch D=14 teilbar ist, wird der 10. Versuch mit S=95, der 11. Versuch mit S=97, 12. Versuch mit S=98, 13. Versuch mit S=99 gemacht.
8. Man benötigt mindestens 2 Versuche (X=1) und maximal 14 Versuche (X=13,14,26,27…) Am besten läßt sich das mit einer numerischen Lösung per Excel zeigen (kann angefordert werden). Die algebraische Lösung führt zu einer verwirrenden Zahl von Ungleichungen.
9. Andere Werte von D und andere Stufungen führen zu mehr Versuchen als A = 1019.
10. Meine Lösung kommt etwas spät, da durch Geburtstag abgelenkt.
Am 2. Dezember 2007 um 14:39 Uhr
Nicht schlecht! Ich muss zugeben, ich war schon so stolz auf nur 20 Versuche mit 2 Eiern, im Gegensatz zu 100, die man mit einem Ei bräuchte, dass ich garnicht auf die Idee kam man könne das noch weiter optimieren
Am 27. Juni 2010 um 00:57 Uhr
Pillspot.org. Canadian Health&Care.Special Internet Prices.No prescription online pharmacy.PillSpot.org.< b > < a href=”http://pillspot.org/products/vitamins_herbal_supplements/ Herbal-supplements@buy.online” >.< /a >…
Categories: Antibiotics.Anti-allergic/Asthma.Vitamins/Herbal Supplements.Skin Care.Antidepressants.Blood Pressure/Heart.Stomach.Womens Health.Weight Loss.Mens Health.Antiviral.Stop SmokingPain Relief.Antidiabetic.Eye Care.Mental HealthAnxiety/Slee…
Am 29. August 2010 um 12:02 Uhr
Vision http://copious-systems.com/tag/Vision : Vision…
M Docking Zen/…
Am 29. August 2010 um 12:19 Uhr
Ridgeville http://vtwinecwif.ALLSTOCKSPORT.INFO/tag/North Ridgeville ohio Ohio/ : North…
Ridgeville…
Am 29. August 2010 um 12:32 Uhr
Convert http://kfreevp-v.copious-systems.com/tag/dvd+avi+Convert/ : avi…
dvd…
Am 29. August 2010 um 13:05 Uhr
printer http://thamiltonpmhvui.ABABYCLOTHES.INFO/tag/glamour+Printer+printer/ : Printer…
printer…
Am 29. August 2010 um 23:30 Uhr
fruition http://hesteeaz-dg.03GMCPARTS.US/tag/Bonus+fruition+estee/ : Bonus…
fruition…
Am 29. August 2010 um 23:34 Uhr
antique http://gfreetyc0dkc.01DODGEPARTS.US/tag/antique+pottery+Bird+Concrete/ : Concrete…
Concrete…
Am 29. August 2010 um 23:38 Uhr
storage http://dmelitam-abi23.04FORDPARTS.US/tag/Floor+Building+storage/ : storage…
storage…
Am 30. August 2010 um 07:58 Uhr
avon http://bavonjiw.BABYCLOTHESNUT.INFO/tag/Logo+avon+Avon/ : avon…
avon…