3. Rätsel

Rätsel

  • F

    TGGC schrieb:

    @MrN: Keine Ahnung, die Regel hat mal irgendwer weiter oben aufgestellt und ich finde sie recht sinnvoll, die kenne ich schon aehnlich aus Grundschule Mathematik. f'`8k

    ich habe das mal so gesagt, bei der Aufagbe wo man die diese rote Linie da berechen musste.
    OK: Edit zu den Regen: Der Aufgabensteller soll in sein Rätsel reinschreiben ob raten erlaubt oder verboten ist.
    Ich persönlich bin dagegen, aber das soll jeder selbst entscheiden.

    0
  • D

    Fein 🙂

    TGGC möchte alleine einen 1000km langen Weg durch das Himalaya wandern. Pro 1km braucht er ein 100g schweres Verpflegungs-Pack mit Essen und Trinken. Obwohl er unglaublich stark ist, kann er nur 500 Packs gleichzeitig tragen (er kann also das Himalaya nicht auf einmal durchqueren, sondern muß an geeigneten Stellen Lager errichten und öfter umkehren). Wie viele Vorratspacks braucht er mindestens um das Himalaya zu durchqueren?

    EDIT: Werte geändert, um Diskretisierungsfehler klein zu halten.

    0
  • F

    er läuft mit den ersten 500 packs 500 km weit. dort macht er pause und kauft sich 500 packs mit denen er dann die restlichen 500 km läuft. er brauch also 100 packs

    0
  • B

    Wo soll er sich mitten im Himalaya Essen kaufen? Er wird erst 125 km laufen, dort 250 Packen hinlegen, mit den restlichen 125 Packen zurücklaufen, das macht er 16 mal, dann sind im ersten Lager schon mal 4000 Packen Essen 😮 😃 Er füllt sich da seinen Rucksack wieder auf (noch 3500 Packen im Lager), läuft 125 km und errichtet da sein zweites Lager. Da legt er 250 hin und läuft zum ersten Lager zurück; das Ganze noch sieben mal, im ersten Lager is nu nix mehr, im zweiten Lager liegen 2000 Packen und er hat noch 750 km vor sich. 125 km weiter (bei 375 km) legt er wieder ein Lager an, wo dann 1000 Packen liegen. Im nächsten Lager, bei 500 km liegen dann 500 Packen. Ab da kann er dann durchlaufen. Er braucht also mindestens 4000 Packen Essen und legt mindestens 4000+2000+1000+500 = 7500 Kilometer zurück.
    Auch wenns falsch ist, schönes Rätsel 🙂

    Ne irgendwas ist falsch dran, überall einen Weg zuviel berechnet 😕

    0
  • B

    Dasselbe wie eben, nur wenn er sein Essen ins erste Lager geschafft hat, hat er ja noch 125 Packen im Rucksack, schließlich muss er ja nicht mehr ins Basis-Lager laufen. Das Ganze vier mal, dass er einen Rückweg nicht braucht, also braucht er nur 3500 Packen Essen.

    Ach dann muss er ja auch weniger Essen in die Lager bringen, Mensch ist das kompliziert... 🙂

    0
  • 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
Anmelden zum Antworten