3. Rätsel

Rätsel

  • B

    Mal andersrum:
    Bei Kilometerstein 500 braucht er noch 500 Packen Essen. Dabei muss er erst 250 hinbringen und mit 250 da ankommen, bei Kilometer 375 muss er also 875 Essen haben (500 zum 250-Packen-eins-weiter-bringen, 125 zum hinlaufen und 250 muss er dann noch im Rucksack haben).

    Weil er beim Lager "375" also 875 Essen haben muss, muss er 500 hinbringen und beim (letzten) Ankommen noch 375 im Rucksack haben. Um 500 hinzubringen, braucht er 1000 Essen. Bei Kilometer 250 braucht er demnach 1000+375+125(zum laufen)=1500 Essen.

    Gut, im Lager bei 250 km braucht er 1500 Essen. Dabei muss er 1250 hinbringen und 250 beim (letzten) Ankommen im Rucksack haben. Zum hinbringen der 1000 braucht er 2000 Essen, bei 125 km müssen dann 2375 Essen liegen.

    Zum hinbringen der 2000 Essen muss er 8 mal laufen (hin und zurück), verbraucht dabei 4000 Essen. Dazu noch 375, die er beim Ankommen im Rucksack haben muss, macht dann 4500 (muss ja noch mal hinlaufen) 🕶

    0
  • M

    jo, das rätsel is cool, gibt sogar ne anekdote, nach der sich john f. nash sich mit irgendwelchen studenten wegen soeinem rätseln mal total gestritten habe^^

    ist es eigtl. erlaubt, die rätsel mit computerhilfe zu lösen? ist hier schließlich nen programmierforum und das ist doch ne echte musteraufgabe für backtracking 😉 oder fällt das unter raten? 😞

    0
  • D

    Ich würde programmierte Lösungen schon gelten lassen. Es ist ja immerhin ein Verfahren zur Lösung zu kommen.

    0
  • B

    Heißt das meine Lösung ist falsch? 😞

    0

  • In dem Programm muss dann ja ein Algorithmus zum Loesen des Problemes sein. Solange der deterministisch ist, ist es kein Raten. f'`8k

    Autocogito

    Gruß, TGGC (making great games since 1992)

    0
  • D

    Badestrand schrieb:

    Heißt das meine Lösung ist falsch? 😞

    Du hast eine Lösung zum Problem der Himalaya-Durchquerung gefunden, aber die entscheidende Frage leider nicht beantwortet: geht es auch mit weniger? Wenn ja, warum, wenn nein, warum nicht?

    0
  • B

    Hast Recht, ist suboptimal. Ich glaub aber der Algorithmus übersteigt meinen Horizont 🙂 Naja ich rätsel noch ein wenig rum

    Muss die Anzahl der Päckchen, die er trägt oder irgendwo hinlegt, ganzzahlig sein?

    0
  • J

    TGGC schrieb:

    In dem Programm muss dann ja ein Algorithmus zum Loesen des Problemes sein. Solange der deterministisch ist, ist es kein Raten. f'`8k

    Wobei man durch eine Brute-Force-Lösung zum Beispiel weniger lernt. Man weiß dann zwar, dass man das Optimum hat, aber eben nicht warum. Eine Lösung mit nem cleveren Algorithmus würde ich aber gelten lassen (wenn es meine Entscheidung wäre ;)).

    0
  • M

    TGGC schrieb:

    Daniel E. schrieb:

    Jungs, das ist doch einfach. Das Problem ist symmetrisch, die Vier bilden zu jedem Zeitpunkt ein Quadrat, daß sich um den Mittelpunkt rotiert. Wenn sich, sagenwirmal, Jester um eine Strecke ds Richtung Marc++us bewegt, dann rotiert das Viereck um dphi=ds/s, mit s=Seitenlänge des Quadrats und s nimmt um ds ab. Darum legen sie genau die Seitenlänge des Quadrats zurück (also insgesamt 4 mal die Seitenlänge), bis sie sich in der Mitte treffen.

    Korrekte Loesung. f'`8k

    f'`8k dir selber (was auch immer das heißt). Das ist nicht die korrekte Lösung. Als ich Jester, volkard und Marc++us das letzte Mal gesehen habe, sind sie nicht in infinitesimal kleinen Schritten gelaufen (Hume hab ich noch nie persönlich getroffen aber bei ihm nehme ich das gleiche an). Dass das ein Problem ist, hat camper doch korrekt bemerkt?! Aber ihr vereinfacht die Welt einfach grundlegend und schreibt das dann in der Aufgabe nichtmal dazu. 👎

    0
  • M

    Jester schrieb:

    TGGC schrieb:

    In dem Programm muss dann ja ein Algorithmus zum Loesen des Problemes sein. Solange der deterministisch ist, ist es kein Raten. f'`8k

    Wobei man durch eine Brute-Force-Lösung zum Beispiel weniger lernt. Man weiß dann zwar, dass man das Optimum hat, aber eben nicht warum. Eine Lösung mit nem cleveren Algorithmus würde ich aber gelten lassen (wenn es meine Entscheidung wäre ;)).

    dass der "beweis" dann unschön ist und man das problem damit nicht wirklich durchdringt sehe ich auch so, deshalb hab ich ja gefragt, ob brute-force nicht zu raten zu zählen ist, denn ich könnte ja hier auch einfach immer was reinschreiben und komm dann irgendwann aufs richtige (ist auch deterministisch), wobei die aktion ja zwischendurch illegal wär und erst am ende dann ein ok bekommen würde --> nicht durchfühbar 😃

    ot: ich kenn mich da leider nicht so aus, deshalb mal ne ganz kleine frage: ist jeder algorithmus, der auf nem normalen pc läuft, deterministisch? wenn man dafür keine eingaben von nem user oder so braucht... eigtl. doch schon, oder?

    0

  • Bruteforce ist ja nicht raten, sondern systematisches Probieren. Das mag manchmal aufwendig sein, trotzdem ist es ein korrekter Loesungsweg. f'`8k

    Gruß, TGGC (making great games since 1992)

    0
  • C

    Mr. Pink schrieb:

    ot: ich kenn mich da leider nicht so aus, deshalb mal ne ganz kleine frage: ist jeder algorithmus, der auf nem normalen pc läuft, deterministisch? wenn man dafür keine eingaben von nem user oder so braucht... eigtl. doch schon, oder?

    Wenn du Zufallszahlen oder Pseudo-Zufallszahlen verwendest, gilt ein Algorithmus in diesem Sinne nicht mehr als deterministisch.

    In diesem Zusammenhang könnte man deterministisch aber auch sehen als: Der Algorithmus liefert stets das gleiche Ergebnis, wenn die Eingabedaten die gleichen sind. Intern dürfen dann auch (Pseudo-)Zufallszahlen verwendet werden, solange die keinen Einfluss auf das Ergebnis haben, sondern höchstens auf die Laufzeit.

    0
  • B

    Aaaaalso, fangen wir wieder bei 500km an, ab dem Lager hier soll er die 500 verbleibenden km durchlaufen, dafür braucht er 500 Pakete.
    Die setzen sich zusammen aus dem, was er im Rucksack hat und dem, was im Lager ist.
    Also
    Needs = Lager + Rucksack
    mit
    Needs = 500
    Lager = (500-2*Strecke_vom_letzen_Camp)*Transporte
    Rucksack = 500-Strecke_vom_letzen_Camp
    ergibt
    Strecke_vom_letzen_Camp = (500(Transporte+1)-Needs) / (2Transporte+1)
    mit 0<Strecke_vom_letzen_Camp<250

    Im folgenden ist
    W = Weg = Strecke_vom_letzten_Camp
    N = Needs
    T = Transporte

    Für das Stück vom zweitletzten Lager (II) bis zum letzten Lager (I, bei 500km) ergibt die Strecke für die kleinste Zahl der Transporte(T=1) W=500/3, also ~166.
    Am letzten Lager hat er dann also 1*166 Essen hingebracht und 333 im Rucksack.
    Lager I ist also bei 500 km
    Lager II bei 334 km

    Also beträgt das Needs des Lagers II 1000 Essen.

    Von Lager III zu Lager II beträgt mit Needs=1000 beträgt das kleinste ganzzahlige T: T=2 mit W=100. Er hat also 2 mal Essen transportiert (je 300) und nach dem letzten Laufen zu Lager II hat er noch 400 im Rucksack.
    Lager III bei 234 km

    Needs( Lager III ) = 1500
    Kleinstes T=3 mit W=500/7 ~= 71
    er bringt 3*~358 (wegen 500-2*71) Essen und hat ~429 im Rucksack. Das ergibt inkl Weg für Lager IV ein Needs von 2000.
    Lager IV bei 163 km

    Needs( Lager IV) = 2000
    Kleinstes T=4 mit W=500/9 ~= 56
    4 Transporte mit je 500 Nahrung und er muss mit 500 losstiefeln, ergibt 2500.
    Lager V bei 107 km

    Needs( Lager V) = 2500
    Kleinstes T=5 mit W=500/11 ~= 45
    Lager VI bei 62 km

    Needs( Lager VI ) = 3000
    Kleinstes T=6 mit W=500/13 ~= 38
    Lager VII bei 24 km

    Needs( Lager VII ) = 3500
    Kleinstes T=7 mit W=500/15 ~= 33 von verbleibenden 24 km

    Wegen den paar km zuviel können wir wegen 15 zu laufenden Strecken die Differenz 15*(33-24) = 135 Nahrung abziehen, also braucht TGGC insgesamt, mit Rundungsfehlern, 3365 Nahrung!

    Und wer hier keinen Algorithmus erkennt, der ist doof 🤡

    edit: Man rechnet also die Strecken mit
    sum=∑i=0∞5002∗i+1sum = \sum_{i=0}^\infty \frac{500}{2*i+1} zusammen, bis die Strecke >= der gewünschten Strecke (hier 1000 km) ist. Der Soll-Wert der Pakete beträgt dann (i+1)∗500(i+1)*500. Davon muss man noch den Überschuss abziehen:
    (2\*i+1) \* (LetzteErrechneteStrecke - LetzterStreckenRest)

    edit: habs mal programmiert

    int CountPakete( int strecke )
{
	double sum = 0;
	for ( int i=0; sum<strecke; i++ )
	{
		sum += 500. / (double)(2*i+1);
	}
	i--;
	int pakete = (i+1)*500 - ((int)sum-strecke)*(2*i+1);
	return pakete;
}

    => 3850, hab ich mich wohl oben verrechnet :p

    edit: im c++-Code hat was nich gestimmt...

    0
  • C

    Badestrand schrieb:

    Aaaaalso, fangen wir wieder bei 500km an, ab dem Lager hier soll er die 500 verbleibenden km durchlaufen, dafür braucht er 500 Pakete.

    [...]

    Woher weißt du dass die optimale Lösung ein Lager bei Position "500km" haben muss? Vielleicht braucht man weniger Pakete, wenn man an der Stelle kein Lager aufschlägt.

    0
  • B

    Christoph schrieb:

    Woher weißt du dass die optimale Lösung ein Lager bei Position "500km" haben muss? Vielleicht braucht man weniger Pakete, wenn man an der Stelle kein Lager aufschlägt.

    Na gut, wissen tue ich es nicht, ich vermute es aber 🤡 Schließlich muss man den Rucksack optimal ausnutzen, um gut vorwärts zu kommen, die Lager bzw das Füllen des Lagers bilden den Flaschenhals.
    Aber mit dem Algorithmus fängt man eigentlich auch gar nicht bei 500 km an, sondern bei 1000km. Ab da geht man rückwärts und der Algorithmus sagt, das letzte Lager vor Ziel wäre bei 500 km 🙂

    Und wenn man ein Lager hinter der 500-km-Grenze machen würde, macht das doch keinen Sinn. Um ein Lager zu errichten, muss man mehr als 500 Pakete dahinschaffen, sonst braucht man ja kein Lager. Und hinter der 500-km-Grenze braucht man definitiv keine 500 Pakete an Essen/Trinken mehr, deshalb nützt das Lager ja nix...

    0
  • J

    Warum? Warum? Warum?

    0

  • Ich im Himalaya? Muhahaha ;).

    Mr. N schrieb:

    f'`8k dir selber (was auch immer das heißt).

    http://www.games-net.de/hosted/tggc/trash/serious.gif f'`8k

    Gruß, TGGC (making great games since 1992)

    0
  • B

    Jester schrieb:

    Warum? Warum? Warum?

    Ein Lager braucht er doch mindestens vor der 500km-Grenze, sonst verhungert TGGC auf der Hälfte.
    Bevor er zusätzlich noch ein Lager hinter der 500km-Grenze aufschlägt, ist es immer günstiger, das Lager auf der Grenze zu bauen und ab da durchzulaufen.
    Mit einem Lager bei 500-x km (x>0), in dem n Pakete lagern (n>500):

    Transporte (T) zum Lager = n/500
    ~Falls n%500=0, gilt T=n/500-1, was aber die folgenden Rechnungen nicht beeinflusst, schließlich gilt auch dann noch T>0, das erste Lager liegt ja vor der Hälfte.~

    Für jeden Transport fallen Strecke*2 Pakete an Nahrung ab, es kommen also 500-(2*Strecke) Nahrung zum Einlagern an. Mit dem finalen hinlaufen zum Lager brauchen wir nocheinmal [Strecke] Pakete.
    Falls y%500<x, reicht die Nahrung nicht mehr zum Laufen ins Lager, wir übertragen beim Transport vorher einfach entsprechend weniger, kommt dann aufs Gleiche raus.

    • Falls wir nun bis zum Lager bei 500km transportieren:
      Da Strecke hier gleich x ist, werden für den Weg (T*2+1)*x Pakete verbraucht. Die verbleibende Paketanzahl n−(2T+1)xn-(2T+1)x muss größer oder gleich 500 sein, also 500<=n−(2T+1)x500 <= n - (2T+1)x, der Paketbestand im Lager bei 500-x km muss größer oder gleich 500+(2T+1)x500 + (2T+1)x sein.
    • Falls wir aber zum Lager laufen, dass weiter als 500km liegt, also bei 500+y km (y>0):
      Die Strecke beträgt hier y+x, es werden für den Weg (T*2+1)*(x+y) Pakete verbraucht. Es müssen mindestens (500-y) Pakete übrigbleiben, also müssen im Lager bei 500-x km mindestens 500−y+(2T+1)(x+y)500-y+(2T+1)(x+y) Pakete sein, umgeformt 500+(2T+1)x+2Ty500+(2T+1)x + 2Ty.

    Da T>0 und y>0, braucht man definitiv mehr Pakete.

    0
  • D

    Ich denke mal, daß kann man so stehen lassen, ganz formal sauber bewiesen muß es ja nicht sein (hier ist ja nicht das Matheforum). Zahlenwerte rechne ich außerdem nicht nach (da gibt's etwas Interpretationsspielraum: ißt er das Pack am Anfang des Kilometers oder am Ende oder kontinuierlich? Kann man Lager bei halben Kilometern aufbauen? Kann er angebrochene Packs essen? etc.) aber das Teilungsprinzip ist richtig.

    Es ist halt wichtig, daß man versteht, daß TGGC an jedem Kilometerpfeiler eine ungerade Anzahl oft vorbeikommt, an den letzten Kilometermarkern aber nur einmal. Darum versucht man den letzten Teilabschnitt so groß wie möglich zu machen. Dieses Schema setzt man rekursiv fort. Google kennt das als "Jeep problem" und ist mathematisch gar nicht mal so einfach.

    0
  • B

    Juchu! 🙂 Ich geb das Rätsel-stellen aber ab, ich kann die mir genauso schlecht merken wie Witze 😕

    0
Anmelden zum Antworten