3. Rätsel

Rätsel

  • 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
  • F

    das heißt der nächste darf, und das bin ich!
    mal ein (leichter)Test ob ihr die Formel zum berechnen von der fibonacci Folge.

    Sag die Formel, wo mit man sofort das n-te Glied bestimmen kann.
    Folge:
    2,2,4,6,10,16,26,32, usw....

    0

  • Fussel schrieb:

    das heißt der nächste darf, und das bin ich!
    mal ein (leichter)Test ob ihr die Formel zum berechnen von der fibonacci Folge.

    Sag die Formel, wo mit man sofort das n-te Glied bestimmen kann.
    Folge:
    2,2,4,6,10,16,26,32, usw....

    Ich verstehe noch nicht mal, wie man auf 32 kommt?! f'`8k

    Gruß, TGGC (making great games since 1992)

    0
  • C

    TGGC schrieb:

    Fussel schrieb:

    das heißt der nächste darf, und das bin ich!
    mal ein (leichter)Test ob ihr die Formel zum berechnen von der fibonacci Folge.

    Sag die Formel, wo mit man sofort das n-te Glied bestimmen kann.
    Folge:
    2,2,4,6,10,16,26,32, usw....

    Ich verstehe noch nicht mal, wie man auf 32 kommt?! f'`8k

    Vermutlich ein Schreibfehler (@Fussel: 16+26=42)

    Zum Rätsel selber: Deine Folge ist das doppelte der "normalen" Fibonacci-Folge, also muß man auch die allgemeine Formel dafür mit 2 mutliplizieren:

    an = 2*(Φn-Ψn)((Φ-Ψ)

    0
  • U

    macht doch mal ein rätsel, bei dem man mit mathe nicht weiterkommt 🙂

    0
  • ?

    Kannst du haben (ich bin zwar nicht dran, aber wenn es interessiert ... Das habe ich mir vor Jahren mal in Andacht an den "kleinen Hobbit" ausgedacht, wo es ähnliche Rätsel vom Stil her gab):

    "Aus Technik geboren und äußerlich bunt,
    war es Jahre in Erzeugung,
    ist es schlau und doch dumm!
    Es hat kein Gedächtnis
    und trotzt doch manchem Gehirn;
    hält jahrelange Arbeit
    verschlossen in Ehr'n."

    0
  • F

    jaja ich meinte 42 :D:D:D
    cstol hat nartürlich ... 😞

    zu a....:
    das muss ein Roboter sein
    lange geforscht, bunt angemalt usw...
    aber cstoll soll ers n neues Rätsel machen...

    0
  • C

    Undertaker schrieb:

    macht doch mal ein rätsel, bei dem man mit mathe nicht weiterkommt 🙂

    Na gut, ich versuch's:

    Zehn Vögel sitzen auf einer Hochspannungsleitung. Da kommt TGGC mit der Schrotflinte und schießt einen ab. Wieviele Vögel sitzen jetzt noch auf der Leitung?

    0
  • F

    der war bilig
    keiner, da die anderen Vögel sich erscheckt haben und weggefolgen sind. 😉

    0
  • M

    Keiner.
    Die fliegen alle weg 🙂

    //EDIT:
    Verdammt zu spät 😡

    0
  • C

    Ich wußte, es war zu einfach 😃

    0
  • ?

    @Fussel
    Falsch. 😉

    0
  • C

    arnyek: eine CD

    0
Anmelden zum Antworten