19: Kirschwein / Cherry Wine

  • ...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)

    Wenn du so wie ich weiter gedrittelt hättest, wärst du am Ende auf 16 MWh gekommen.

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

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

    Wenn man die Idee für die erste Zeile hatte, war man einen großen Schritt weiter. Die zweite Zeile ergibt sich dann durch "geschicktes Testen".

    Damit kann man sich dann ohne weitere Probleme vom Start bis zur Lösung vorarbeiten, völlig ohne Fibonacci.


    Aber der Schritt von "Kosten für x Flaschen" zu "max. Zahl der Flaschen mit Kosten n" ist nicht offensichtlich. Wer den nicht gefunden hat, sollte sich freuen, dass er diese Technik jetzt kennt, diese Einsicht gewonnen hat. Solche Wechsel der Sichtweise braucht man immer wieder in der Mathematik.

  • Wenn du so wie ich weiter gedrittelt hättest, wärst du am Ende auf 16 MWh gekommen.

    ...wäre ja aber auch falsch gewesen... ;-)


    Ich hatte 377 —> 126 —> 42 —> 14 —> 5 —> 2 —> 1 und brauche 5 Drittelungen (incl. „Aufrundung“ der gedrittelten Menge vor dem nächsten Dritteln) zu je 3MW und 1 Halbierung am Ende zu 2MW = 17.


    Wo ist da mein Denkfehler?

  • ...wäre ja aber auch falsch gewesen... ;-)


    Ich hatte 377 —> 126 —> 42 —> 14 —> 5 —> 2 —> 1 und brauche 5 Drittelungen (incl. „Aufrundung“ der gedrittelten Menge vor dem nächsten Dritteln) zu je 3MW und 1 Halbierung am Ende zu 2MW = 17.


    Wo ist da mein Denkfehler?

    Leider bin ich auch nicht auf die optimale Strategie gekommen.


    Ich habe übersehen, dass ich bei 5 nicht mehr gedrittelt habe sondern "halbiert". Wenn man dann die Gruppe mit den 2 Flaschen zuerst testet, kommt man schlimmstenfalls auf 4MWh.

    - Ist der Kirschwein in der 2-er Gruppe, hat man 2Mwh verbraucht und muss nur noch 1 Mal testen.

    - Ist der Kirschwein in der 3-er Gruppe, hat man 1Mwh verbraucht und muss nur noch 2 Mal testen.

  • Ich habe übersehen, dass ich bei 5 nicht mehr gedrittelt habe sondern "halbiert". Wenn man dann die Gruppe mit den 2 Flaschen zuerst testet, [...]

    ...[...] dann hättest Du fast sogar schon die richtige Lösung gehabt. Da bin ich aber auch schon nicht drauf gekommen.

    Hier zeigt sich, dass „bewährte“ Verfahren durchaus mal hinterfragt werden können. Wenn ein Test allerdings nur 1W / 2W „kostet“, dann hat man durch das Überlegen mehr Ressourcen „verballert“ als ggfls. eingespart... Und im Mittel ist das Halbieren ggfls. sogar besser...