19: Kirschwein / Cherry Wine

  • Ganz tolle Aufgabe! Großer Dank an die Herren Woeginger/ Blokhuis.

    Großer „Aha-Effekt“, wenn man auf einmal auf die Fibonacci-Folge stößt, wo zumindest ich sie anfangs gar nicht auf dem Schirm hatte! Letztendlich liegt der Grund dafür an der Tatsache, dass man, je nachdem ob die MKTM rot oder grün leuchtet, ein ODER zwei Mwh verbraucht: bedeutet bei induktiver Betrachtung, dass man ein oder zwei „Bereiche“ zurückspringt...


    Hier ein Lösungsvorschlag mit genaueren Erläuterungen:

    https://www.dropbox.com/s/0fjo…chwein_Fibonacci.JPG?dl=0

  • Also bei mir war das Aha-Erlebnis, dass die Aufteilung der Gruppen nach dem "goldenen Schnitt" gemacht wird.

    Das ergibt sich aus der Suche nach einem optimalen Splitting durch


    p = (1-p)^2 => p=3/2 - sqrt(5)/2, hier die relevante Lösung. Das ist der goldene Schnitt.


    Damit hat man als Gruppensplittings, super konstruierter Startwert 377 => 144 => 55 => 21 => 8 => 3.


    Von den Verbleibenden muss man schlimmstenfalls mit 2+1 Einheiten rechnen.


    Insgesamt also 5*2+3 = 13 Einheiten.

  • Ich hatte das programmiert. Und dann habe ich untersucht, welche Flaschenmenge sich mit soviel Energie testen lässt. Und dann mit 1 MWh weniger ...

    So bin ich auch auf die Fibonacci-Folge gestoßen:

  • F(n)= max. Zahl der Flaschen, die mit n MWh sicher identifizierbar sind,

    dann gilt F(n)=F(n-1)+F(n-2)

    F(0)=F(1)=1


    Allgemein: F(n)=F(n-k1)+F(n-k2), wobei k1und k2 die Kosten sind.


    Mit anderen Kosten wurde die Aufgabe schon mal bei PuzzleUp gestellt, was mir aber erst nach dem Lösen aufgefallen ist...

  • Also bei mir war das Aha-Erlebnis, dass die Aufteilung der Gruppen nach dem "goldenen Schnitt" gemacht wird.

    Das ergibt sich aus der Suche nach einem optimalen Splitting durch


    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

  • Ah ja.... Kennen 10.-Klässler üblicherweise schon Fibonacci-Folgen, oder können sie alternativ allesamt programmieren?

    Die müssen sie ja nicht vorher kennen.


    Ich überlege mir ja, wieviele Flaschen ich mit einer MWh sicher erkenne, mit 2, mit 3 usw. Und kann dann erkennen, dass ich Zahlen, die ich schon kenne, addieren muss.

    Dann sollten auch sie irgendwann das System erkennen und einfach weiter addieren.


    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.


    Ich muss gestehen, dass ich erst an der Stelle das Deja-Vu hatte, genau den Denkprozess schon mal durchlaufen zu haben.

  • p = (1-p)^2


    Ok, da steh ich noch aufm Schlauch, wieso das ein Ansatz sein soll, und warum der Goldene Schnitt überhaupt relevant ist, nachdem da Wurzel aus 5 drin vorkommt und diese keine ganze Zahl ist, die Flaschenanzahlen also nur irgendwas "Gerundetes" darstellen können und somit für mich nicht ersichtlich ist, dass/warum das dann "ideal" sein soll.

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

    Aber nein. Man sieht doch schnell ein, dass die optimale Strategie nicht immer halbieren darf (weil im einen Fall 2 MWh und im anderen Fall nur 1 MWh verbraucht werden). Dann muß man sich überlegen, wie groß die beiden Gruppen relativ zu einander sein sollen. Dann probiert man lange herum und findet die Aufteilung. Das Aha-Erlebnis bei diesem Rätsel war wunderschön!

  • Nun, ich hatte die ganze Zeit die Aufteilungen irgendwie gedrittelt, wegen diesem Verhältnis 2:1.

    Dass es so ein "komisches" Aufteilungsverhältnis sein soll, hat sich mir absolut nicht erschlossen, und mir ist auch jetzt noch nicht klar, woraus ich das folgern hätte sollen, aber ich schau dazu später mal ins Lösungsheft, vielleicht kommt der Aha-Effekt ja noch!

  • Nun, ich hatte die ganze Zeit die Aufteilungen irgendwie gedrittelt, wegen diesem Verhältnis 2:1.

    Dass es so ein "komisches" Aufteilungsverhältnis sein soll, hat sich mir absolut nicht erschlossen, und mir ist auch jetzt noch nicht klar, woraus ich das folgern hätte sollen, aber ich schau dazu später mal ins Lösungsheft, vielleicht kommt der Aha-Effekt ja noch!

    Du kannst dich auch von unten nach oben arbeiten:

    • Zuerst versuchst du, die Aufgabe mit 3 statt 377 Flaschen zu lösen; da entdeckst du dann die 1:2 Aufteilung.
    • Dann versuchst du, die Aufgabe mit 5 statt 377 Flaschen zu lösen; da entdeckst du dann die 2:3 Aufteilung.
    • Dann versuchst du, die Aufgabe mit 8 statt 377 Flaschen zu lösen; da entdeckst du dann die 3:5 Aufteilung.
    • und so weiter.

    Dazwischen sind die einfacheren und uninteressanten Fälle mit 4,6,7 usw Flaschen zu behandeln.

  • Für die 3 und die 5 hatte ich das sogar, aber dass ich dann 3 und 5 addiere und warum, das konnte sich mir nicht erschließen, und das sehe ich immer noch so. Für mich ist es grad mega frustrierend, dass ich alle 3 schweren Aufgaben, die hintereinander kamen und für die ich ein Vielfaches an Zeit aufgewendet habe als für alle anderen zusammen, letztlich nicht lösen konnte (gut, für die Mützenaufgabe hatte ich immerhin so eine mittelmäßige, nicht optimale "Teil-Lösung"; bei Xmasium vertraute ich meiner Intuition bzgl. Nicht-Lösbarkeit nicht), das macht grad einen richtig miesen Nachgeschmack. Auch tun mir die Zehntklässler leid, die vermutlich erst recht Probleme damit gehabt haben dürften, insbesondere bzgl. Durchhalten nach soviel Frust in Folge.

  • Ich peils immernoch nicht.

    Die erste Aufteilung ist 377=144+233.

    Im worst case ist der Kirschwein in der größeren 'Hälfte' und hat 2kWh verbraucht. Wenn das dann immer so weitergeht (also größere Hälfte und maximaler Verbrauch) komme ich am Ende auf viel mehr kWh. Wo ist mein Denkfehler?

    Du testest 144 Flaschen in der Maschine; also nur den kleineren Teil der Aufteilung.

    • Wenn grün: Kostet 2MWh und nur 144 übrig.
    • Wenn rot: Kostet nur 1MWh und noch 233 übrig.