Der logarithmische Bierkeller

[tomS]

Der logarithmische Bierkeller

Nachdem ich aus Franken, der Gegend mit der nachweislich höchsten Brauereidichte der Welt, komme, hier ebenfalls eine Matheaufgabe (Vorsicht: schwierig!)

Franz und Georg sind auf einem Bierkeller (in Franken geht man auf den Bierkeller, nicht in den Biergarten: http://www.bierkeller.de/). Franz geht, um sich eine Maß zu holen und dem Georg ein Seidla (das ist ein halber Liter mitzubringen, weil der nicht so viel verträgt. Dann entscheidet sich Georg aber um und ruft Franz hinterher, dass er lieber eine Radlermaß haben will. Nun ist aber die Maß Bier schon eingeschenkt und Franz sagt, er möchte erst die Hälfte austrinken und sich dann mit Limo wieder nachschenken lassen. Die halbe Bier müsste dann der Georg zahlen.

Nun fängt der Franz zu überlegen an: wenn er z.B. erst ein Viertel austrinkt und sich dann mit Limo nachschenken lässt, dann hat er ja ein Mischungsverhältnis von 3/4 zu 1/4. Wenn er dann wieder ein Viertel trinkt und sich nachschenken lässt, ist er immer noch nicht bei einem Verhältnis von 1/2 zu 1/2 angelangt, d.h. er könnte noch mal trinken und hätte insgesamt mehr als eine halben Liter getrunken (was ja wieder der Georg zahlen müsste).

Jetzt kommt der Franz richtig ins Schwitzen, weil er merkt, dass da Optimierungspotential drin liegt, er aber merkt, dass er das mit „einfach mal so schnell ausprobieren“ nicht hinkriegt. Damit sind wir bei der Aufgabenstellung:
1) Franz möchte mehrfach trinken und sich jedes Mal mit Limo wieder auf einen Lieter nachschenken lassen
2) Franz wird mit dem Trinken aufhören, sobald nach dem Nachschenken mit Limo das Mengenverhältnis 1/2 zu 1/2 erreicht ist.
3) Franz darf nie zu viel trinken, denn es wird immer nur mit Limo und nie mit Bier aufgefüllt; d.h.er darf das Verhältnis 1/2 zu 1/2 nie unterschreiten
4) wie oft und wie viel muss Franz jedes Mal trinken, um die insgesamt getrunkene Menge zu maximieren? und wie groß ist diese Menge?

Viel Spaß

[gradient]

Hallo Tom,

so eine ähnliche Idee hatte ich mir auch mal überlegt, allerdings nichts zum Schreiben parat gehabt. Da hatte ich vermutet, dass es auf geometrische Reihe hinauslaufen würde, aber jetzt habe ich es überprüft, und bin zumindest erfreut, dass Logarithmen vorkommen.
Interessanterweise ist meine Funktion streng monoton fallend und hat so keinen Extremwert.
Das Ergebnis: Es sei die Menge, die er jeweils trinkt, d.h. er füllt danach immer Liter Limo nach. Dann darf er mal Liter trinken. Um auf 0,5 Liter Bier zu kommen, muss er beim letzten Mal Liter trinken.
Ich komme so auf das Ergebnis, dass er insgesamt umso mehr trinken darf, je kleiner x ist. Bei x=0,1 dürften es insgesamt 0,65916 Liter sein. An 1 Liter wird er in der Realität nie herankommen.

Keine Ahnung, ob das stimmt, ist zur Zeit schwer, meinen Übermüdungszustand loszuwerden...

Beste Grüße aus Regensburg (m.W. größe Kneipendichte in Deutschland^^ - was aber nichts mit der Müdigkeit zu tun hat! ),
Patrick

[tomS]

Kleine Ergänzung: es ist nicht gesagt, dass er jedesmal gleich viel trinken wird!

[tomS]

Also ich habe drei Lösungsansätze:
Sichtwort Variationsrechnung mit Nebenbedingung: man betrachte N Schlucke 1..N; man betrachte dabei immer den zu trinkenden Bruchteil; man bestimme die Gesamtmenge X in Abhängigkeit der Schluckgröße; man führe einen Lagrangemultiplikator ein, der dafür sorgt, dass der Anteil Bier zuletzt genau 1/2 beträgt.
Sichtwort kontinuierlicher Flüssigkeitsstrom: man betrachte die zwei Flüssigkeitsströumungen in das Glas hinein (ausschließlich Limo) und aus dem Glas hinaus (Limo-Bier-Gemisch; optimale Durchmischung vorausgesetzt, d.h. die herausströmende Flüssigkeit enthält das selbe Limo-Bier-Verhältnis wie es zu diesem Zeitpunkt im Glas vorhanden ist) und betrachte das Integral über die Zeit.
Sichtwort Computersimulation: man würfle in jedem Schritt eine Zufallszahl, die so beschaffen ist, dass das Limo-Bier-Gemisch auf nie mehr als 1/2 für den Limoanteil führt; man bestimme die Gesamtmenge aus den einzelne Zufallszahlen; man bestimme über viele Durchläufe den Bestwert für die Gesamtmengen.

Für den zweiten Ansatz ist zunächst nicht klar, dass er auf die korrekte Lösung führt. Die Lösung des ersten Ansatzes zeigt aber, dass man im Grenzfall unendlich vieler unendlich kleiner Schlucke das beste Ergebnis erzielt.

[tomS]

Wow! Magst du deinen Rechenweg hier reinstellen? Du warst echt fix!

[tomS]

Ja, so hab' ich mir das auch zusammengereimt.

Eine Frage bleibt noch: wie folgerst du, dass es sinnvoll ist, in jedem Schritt den gleichen Bruchteil x zu trinken? Grundsätzlich könntest du auch bei jedem Trinkvorgang n eine andere Menge x[down]n[/down] zulassen.

[tomS]

Ja, auch da hast du recht. Ich habe das mit Variationsrechnung mit Nebenbedingung (Lagrangemultiplikator) ausgerechnet. Stimmt genau mit deinem Ergebnis überein.Ich werde demnächst die drei genannten Lösungen hier reinstellen.

[tomS]

Hier zunächst mal mein C++ Programm

Code: Alles auswählen

// log_beer.cpp : Defines the entry point for the console application.
//

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>



const unsigned i_max    = 1000001;                  // granularity of random numbers

const unsigned run_max  = 1000000;                  // max. number of runs for sampling
const unsigned step_max =    1000;                  // max. steps per sample run



// generate a random number in [0, 1]
inline double random( double a, double b )
{
    if ( a >= b )
        return 1.0;
    else
        return a + (b - a) * ( double(rand() % i_max) / double(i_max) );
}



// execute one step
inline void exec( double & B, double & L, double & X, bool last_exec = false )
{
    double x_max = 1.0 - 1.0 / (2.0 * B);           // max. quantity of liquid to be consumed in actual step
                                                    // must respect the constraint B_new >= 1/2 

    double x;

    if ( last_exec == false )
           x = random( 0, x_max );                  // random actual quantity of liquid consumed in actual step
    else
           x = x_max;                               // maximal - " -


    B = (1.0 - x) * B,                              // reduce quantity of beer by fraction x
    L = (1.0 - x) * L;                              // reduce quantity of lemonade by fraction x

    double d = 1.0 - (B + L);                       // max. quantity of lemonade to be refilled
           
    X += x;                                         // increase total quantity of consumed liquid
    L += d;                                         // refill lemonade

    return;
}



// simple sampling algorithm
int main(int argc, char* argv[])
{
    srand( (unsigned)time( NULL ) );

    double X_max = 0.0;

    // several runs to find best sample
    for ( int run=0; run<run_max; run++ )
    {
        double B = 1.0,                             // initial quantity of beer
               L = 0.0,                             // initial quantity of lemonade
               X = 0.0;                             // initial quantity of consumed liquid        

        // several steps for each sample
        for ( int step=0; step<step_max; step++ )
            exec( B, L, X, false );                 // random x for each step
        exec( B, L, X, true );                      // maximum x for final step

        // check if new max X
        if ( X > X_max )    
        {
            X_max = X;
            printf( "%ld: %lf\n", run, X_max );
        }
    }
    return 0;
}

sowie ein typisches Ergebnis:

Code: Alles auswählen

0: 0.691085
3: 0.691222
112: 0.691245
252: 0.691273
1456: 0.691275
1799: 0.691276
6153: 0.691315
10888: 0.691336
11957: 0.691337
12030: 0.691359
139275: 0.691360
196635: 0.691375
266718: 0.691424

[gradient]

So wie tensor hatte ich auch meinen Term hergeleitet. Nur den Grenzwert hatte ich vergeigt, obwohl ich auch nach der Regel von de l'Hospital gearbeitet habe, nur hatte ich dann irgendwann den Faktor ln2 vergessen hinzuschreiben, und dann ist 1 rausgekommen...
Dass er immer die gleiche Menge trinken muss, war mir erstmal intuitiv klar, hätte es aber auf Anhieb nicht gut begründen können wie tensor.

Und dein Programm zeigt, dass es sich lohnt, Probleme mathematisch-analytisch anzugehen, um den Arbeitsaufwand zu minimieren.

Ich bin auf die anderen Lösungsansätze gespannt, v.a. auf den Zweiten.

[tomS]

Also zunächst mal ein Lösungsansatz mit Variationsrechnung.

Ich betrachte die im n-ten Schluck getrunkene Menge x[down]n[/down], die Menge Bier B[down]n[/down] und Limo L[down]n[/down] nach dem n-ten Schluck sowie die Gesamtmenge X und B nach N Schlucken. X ist zu maximieren, B muss zuletzt den Wert 1/2 haben. Dazu führe ich die Größe



ein.

Für X und B gilt





Differentation nach dem Lagrangemultiplikator liefert die notwendige Gleichung



Differentation nach x[down]n[/down] und Einsetzen des Ergebnisses für B liefert die Gleichungen



Da die letzte Gleichung für alle n erfüllt sein muss, folgt sofort dass x[down]n[/down] = x für alle n identisch sein muss.

Damit ist



Wegen B = 1/2 kann man aber nun den Lagrangemultiplikator eliminieren und erhält schließlich





Zur Vereinfachung ersetzt man N durch die Variable 1/z



und bestimmt das Maximum der Funktion X(z). DIeses liegt bei z=0, also für N = unendlich viele Schlucke!

Damit ist der letzte Schritt die Berechnung des Grenzwertes X(0). Man erhält

[tomS]

Der andere Lösungsansatz ist komplizierter. Außerdem führt er über die Annahme, dass kontinuierlich getrunken wird.

Ich betrachte die Gesamt-Biermenge B(t) sowie die Gesamt-Limomenge L(t). Außerdem seien mit dem Index + bzw. - die nachgefüllte bzw. die getrunkene Menge je Zeit bezeichnet, d.h.





Für die Zeitableitungen führe ich neue Funktionen ein:





Dabei ist berücksichtigt, dass B(t) nur abnimmt,. während L(t) einen zunehmenden Anteil durch das Nachfüllen sowie einen abnehmenden Anteil durch das Trinken hat.

Für die getrunkene Menge gilt dann



Ich setze nun die Annahme der optimalen Durchmischung ein, d.h. das Verhältnis von Bier zu Limo ist im jeweils getrunkenen Anteil identisch dem Verhältnis im Glas



Damit kann man die getrunkene Menge Limo eliminieren:



Dies setze ich in das obige Integral ein und forme den Integranden wie folgt um:



Damit gilt



Der letzte Term B+L ist jeweils die Gesamtmenge an Flüssigkeit im Glas. Ich spare mir hier den Beweis, dass das Integral den maximalen Wert annimmt, wenn ich B+L immer gleich Eins setze. Intuitiv ist das klar; es entspricht der Vorgehensweise, nach jedem Schluck wieder vollzuschenken. D.h. aber mit B+L = 1 bin ich schon fertig!



Nun setze ich B(t) = 1/2 und B(0) = 1 ein und erhalte wieder



Zum Beweis, dass L+B = 1 tatsächlich das Integral maximiert: Man setzt dazu B+L = 1-D und zeigt, dass das Integral für D=0 den maximalen Wert hat. D entspricht dabei der Menge, die auf Eins also zum vollen Glas jeweils fehlt. Man kann das resultierende Integral so umformen, dass gilt



Führt man nun eine Variablensubstituation von s nach B(s) durch, so erhält man



Die Variablensubstituation ist erlaubt, da B(s) eine streng monitone Funktion ist. Das letzte Integral ist aber sicher strikt positiv, da sowohl B als auch D positiv sind. Maximales X erhält man für minimales D, also D=0.

[kostja]

Wenn ich Franz wäre, würde ich mit dem ersten Schluck 1/2 L Bier trinken und dann nachschenken lassen. Denn sonst müsste ich das gepanschte Zeug saufen müssen.

Nette Aufgabe

Grüße
Konstantin

[tomS]

Meinst du, das ist auch was für die Knobelecke auf dem Matheplaneten?

[kostja]

Ich weiß nicht. Ich lese nicht viel in der Knobelecke.