19: Kirschwein / Cherry Wine

  • Das kommt ja auch nicht von ungefähr: Es gibt einen sehr schönen Zusammenhang zwischen dem goldenen Schnitt und den Fibonacci-Zahlen:
    Der Quotient f(n+1)/f(n) konvergiert recht flott gegen den goldenen Schnitte (Phi).


    Eine sehr nette Anwendung dieses Sachverhalts: Allen werden ja die Flächenmagietricks: Schokoladenstück verschwindet bekannt sein (gibt s auch auf youtube) Dies geht immer genau mit "Fibonacci-Seitenrändern" der Schokoladentafel... ;):


    https://www.dropbox.com/s/83g3…ci-Flaechenmagie.png?dl=0

    konkret für die Aufgabe Kirschwein: Die erste Aufteilung: 144 - 233 Flaschen (144 testen): ist im Quotient schon auf 4 Nachkommestellen genau der goldene Schnitt: Quotient aufeinanderfolgender Fibonaccizahlen. F(12)/F(11)=233/144 ungefähr 1,6180 ...


  • Auf diese Aufteilung und alle weiteren "einfach so" zu kommen, ist entweder irrsinnig gutes Glück beim Raten oder eben Programmiergeschick.

    Ich bin wie folgt an die Aufgabe gegangen: man muss irgendwie eine sinnvolle (Auf-) Teilung der Flaschen finden. Erster Versuch ist Halbierung, aber dann merkt man, dass das wegen der Kosten die eine Hälfte zu Kosten von 1 ermittelt, die andere zu 2. Also ist die Überlegung, dass man eine etwas unsymmetrische Aufteilung wählt, so dass man die größere Menge mit Kosten von 1 erzeugt, die kleinere Menge mit Kosten von 2. Erstes Probieren mit einem 2:1 Ansatz (einfache Rechnung oder Excel) führt aber dazu, dass man je nach Ausgang mit einem Aufwand von 2 unterschiedliche große Mengen an Flaschen übrig behält. Und das führt dann zu der Überlegung, dass man den Schnitt so wählt, dass p = (1-p)(1-p) ist. Also, die 2 wird mit Wahrscheinlichkeit p produziert, oder eben zweimal auf dem alternativen Weg mit den Kosten von 1. Daraus lässt sich p ermitteln und dann kann man die Fibonacci-Folge rückwärts ermitteln (ohne sie kennen zu müssen). Aber wenn man die kennt, ist der Aha-Effekt ein schöner Nebeneffekt.

  • Ich denke, der Knackpunkt ist, dass man nicht von den (vorhandenen) Flaschen ausgehen darf, um die Kosten herauszufinden, sondern zu den (möglichen) Kosten induktiv die maximale Flaschenzahl bestimmen muss und dabei irgendwann die Zahl der vorhandenen Flaschen überschreitet. Dann hilft einem die Kenntnis der F. etwas, aber nur beim Abkürzen.

    Man kann auch einfach mal mit kleineren Anzahlen anfangen und ausprobieren: 2 Flaschen, 3 Flaschen, 4 Flaschen usw.

  • Wie ich das verstanden habe: Die Hauptstadt in Südostasien ist Hanoi und erinnert an die Türme von Hanoi (wo man 2^n Züge braucht), die Stadt in Südeuropa ist Pisa und erinnert an Fibonacci = Leonardo von Pisa.

    Zumindest hat mich das auf die Fibonacci-Zahlen gebracht.

    ...Ahhh. Vielen Dank!


    Und ich war schon total happy, dass ich den "Trick" gefunden habe, dass ich zuerst drittele und dann jeweils halbiere (nach dem ersten Dritteln gibt es ca. 3mal 128 Flaschen; wenn die ersten ca. 128 Flaschen rot sind, dann benötigt man max. 3MW, um das richtige Drittel zu erkennen; weiter Dritteln bringt ggü. Halbieren keinen Vorteil mehr --> 17 MW anstatt 18 MW beim alleinigen Halbieren)

  • ....Und das führt dann zu der Überlegung, dass man den Schnitt so wählt, dass p = (1-p)(1-p) ist...

    genau, aber Deine Gleichung ist ja gerade DIE CHARAKTERISTISCHE Gleichung des goldenen Schnitts: p^2 - p - 1 = 0
    Lösung 1/2 * (1 +/- sqrt(5)). Und da stecken wie oben beschrieben ja auch die Fibonacci-Zahlen drin (Quotientenfolge konvergiert gegen gold. Schnitt):
    Alles hängt also direkt miteinander zusammen. Wo man anfängt ist eigentlich egal... hübsch das!

  • Aaaah…

    Fibonacci-Folge erkannt, Induktion durchgeführt, komplett richtiger Lösungsweg und dann bei der Obergrenze der "Schachtelungen" um 1 verrechnet und den Vorgang nicht noch einmal "in echt" durchgeführt, weil ich mir bei meiner Lösung so sicher war. Deshalb versehentlich 12MWh statt 13MWh angeklickt, und natürlich mal wieder keine Lose bekommen. So ein Mist aber auch!!! Wie in irgendeiner anderen Lösungsdiskussion schon stand, im Wettbewerb wären das 9,5 von 10, hier aber 0 von 5...

    Ich hasse Multiple Choice, ich könnte mich schwarzärgern, auch wenn es einem die Möglichkeit gibt zu raten, wenn man nicht auf die Lösung kommt...

  • Nicht ärgern, den Fehler machen alle (?) immer wieder und damit mittelt es sich raus. Ausserdem spielst du doch in erster Linie für dich selber, also die Bestätigung, dass du es kannst. Und da kannst du dir doch 9.5 Punkte notieren.

    Wobei ich es als null werten würde. Wenn du die Statik einer Brücke rechnest, und dich entsprechend verrechnet, stürzt sie ein. Und da ist es egal, warum. Genaugenommen finde ich in dem Beispiel 'verschlusselt' sogar schlimmer wie 'zu blöd'.

  • Auf diese Aufteilung und alle weiteren "einfach so" zu kommen, ist entweder irrsinnig gutes Glück beim Raten oder eben Programmiergeschick.

    Bei mir hat es auch 2 Tage gebraucht, um auf die richtige Lösung zu kommen (auch wenn ich letztendlich das falsche angeklickt habe). Zunächst habe ich das ganze auch mit der Aufteilung 2:1 versucht und bin auf eine Menge falscher Lösungen gekommen. Ohne Kenntnis der Fibonacci-Folge hätte ich das auch echt nicht hinbekommen. Außerdem muss ich sagen, die Behauptung, alle Aufgaben seien mit dem Schulstoff der 10. Klasse lösbar, ist schlichtweg falsch. Wer keine Induktion kann (auch ein Prinzip, das in dieser Aufgabe gefordert wird, aber nicht in der Schule drankommt), mag zwar auf die Lösung kommen, kann sie jedoch nicht beweisen (und das ist in der Mathematik ja das wichtigste, auch wenn es hier nicht gefordert ist ;)

    Außerdem finde ich es einfach unnötig, hier andauernd zu behaupten, die Lösungen seien doch "einfach zu finden". Erstens: alle Leute hier im Forum sind, wenn ich mir mal die Listen der besten Teilnehmer der letzten Jahre anschaue, IMO-Teilnehmer, Lehrer, Mathestudenten oder -professoren, ich glaube nicht, dass irgendjemand, der behauptet, die Sachen seien für Zehntklässler lösbar, tatsächlich in der 10. Klasse ist. Ich bin auch in der Zehnten und nehme hier zum ersten Mal teil, aber ich nehme schon sehr lange an der Matheolympiade und beim BWM teil und denke halt, dass nicht alle hier seit Jahren solche Mathe-Freaks sind. Zweitens: Versteht mich bitte nicht falsch, ich mag die Aufgaben, gerade wenn sie so schwierig sind, gerade nach Mathe im Advent in den letzten Jahren ist das eine schöne Herausforderung. Sie sollten meiner Ansicht nicht einfacher sein, aber "für Zehntklässler mit dem Schulstoff lösbar" ist einfach Quatsch - und das ist gut so. Mathewettbewerbe sind auch keine Schulmathematik mehr, und Schulmathematik kann auch nicht ein so schönes Aha-Erlebnis erzeugen wie schöne Beweise nicht aus der Schulmathematik:thumbsup: Ich möchte hier niemanden angreifen, ich finde es aber blöd, wenn hier Neulinge eingeschüchtert werden. Gerade wenn man bei der ersten Teilnahme vielleicht höchstens die Hälfte der Punkte hat (womit ich nicht die Leute meine, die geschrieben haben, sondern mich an die Aussage eines anderen langjährigen Teilnehmers in der Diskussion vom 3. oder 4. Dezember erinnere), motiviert es nicht gerade, weiterzumachen, wenn hier im Forum nur steht, wie schön einfach lösbar die Aufgaben wären.

  • Wie ich das verstanden habe: Die Hauptstadt in Südostasien ist Hanoi und erinnert an die Türme von Hanoi (wo man 2^n Züge braucht), die Stadt in Südeuropa ist Pisa und erinnert an Fibonacci = Leonardo von Pisa.

    Zumindest hat mich das auf die Fibonacci-Zahlen gebracht.

    Nach der entsprechenden Forenaussage hab ich mal auf einer bekannten Karten-Website nach Fibonacci gesucht, und das ist tatsächlich eine türkische(?) Stadt!
    Da hatte ich die Lösung aber schon


    Edit: Ist keine Stadt sondern ein Gebäude, hatte das nur nicht bemerkt

  • Aha-Effekt ist bei mir ausgeblieben, weil man die Sache mit sehr wenigen Zeilen programmieren kann.


    Strategie wie folgt:
    Wenn ich noch n Flaschen übrig habe (von denen eine Kirschwein ist), wieviel Energie muss ich im Worst Case aufwenden, um sie zu identifizieren?


    Für n=1 sind es 0 MWh und für n=2 sind es 2 MWh, das sollte klar sein. Das kann man als Basis für alles weitere verwenden.


    Das Programm hat nun die Aufgabe, den Energieverbrauch für alle Werte n in aufsteigender Reihe zu berechnen, also zuerst n=3, dann n=4, dann n=5 usw.


    Für jedes n geht es dabei wie folgt vor:

    n wird in zwei kleinere Zahlen p und q zerlegt. O. B. d. A. wird p getestet. Es können nun zwei Fälle A und B eintreten. Im Fall A leuchtet die Lampe grün und es werden 2 MWh gebraucht PLUS der Energiewert, den ich brauche, um aus p Flaschen die mit Kirschwein zu bestimmen. Im Fall B leuchtet die Lampe rot und es werden 1 MWh gebraucht PLUS der Energiewert, den ich brauche, um aus q Flaschen die mit Kirschwein zu bestimmen.

    Da wir nicht beeinflussen können, ob Fall A oder Fall B eintritt, müssen wir mit dem ungünstigeren der beiden Fälle rechnen (also der Fall, der mehr Energie braucht).

    Wie wird nun p und q festgelegt? Iterativ. Zunächst ist p=1 und q=n-1, dann ist p=2 und q=n-2 und so weiter. Für jede diese Teilungen in p und q Flaschen bestimmen wir den Energiewert im Wort Case wie eben beschrieben. Dann wählen wir uns von diesen Energiewerten den kleinsten. Warum? Weil die Einteilung in p und q Teil unserer Strategie ist, d. h. wir können willentlich entscheiden, wie groß p und q sind. Deshalb wird Ruprecht später natürlich die Teilung wählen, bei der der Worst Case am wenigsten Energie verbraucht.

    Und damit haben wir unseren Wort Case Energiewert für n :)

    (Ich weiß nicht ob ich das verständlich erklären konnte, aber ich hoffe, man kann es aus dem Code lesen)

  • (Ich weiß nicht ob ich das verständlich erklären konnte, aber ich hoffe, man kann es aus dem Code lesen)

    Ich habe deine Erklärung verstanden. Denn mein zweites Programm hatte ich mit der gleichen Idee erstellt.

    Mein erstes Programm hat eine 1:2 Aufteilung bzw. den als Parameter übergebenen Bruch durchgerechnet und die MWh ausgegeben. Leider hatte ich nur zwei Rundungsmöglichkeiten vorgesehen: aufrunden und abrunden. Mit keiner dieser festen Rundungsarten konnte ich 14 MWh unterbieten. Deshalb dann das zweite Programm.

    Heute habe ich im ersten Programm als feste Rundungsmöglichkeit "runden" programmiert - wie es ja beim Goldenen Schnitt tatsächlich gemacht werden muss. Und prompt erhalte ich auch damit 13 MWh. Beispielsweise bei der Aufteilung 13:21 oder 381:1000 bis 383:1000.

  • Ehrlich gesagt: Die Aussage im Forum, dass man nicht an eine Hauptstadt in Südostasien denken soll, sondern eine Nicht-Hauptstadt in Südeuropa hat mich auf die Lösung gebracht.

    Schön, dass dir mein eher "kleiner" Tipp etwas weitergeholfen hat. Aber dazu muss schon noch wissen, dass Fibonacci eigentlich Leonardo von Pisa hieß. Sein Kaninchen- Problem hat er übrigens in seinem Buch "liber abaci" bereits 1202 veröffentlicht. :)