Aufgabe 10

[Anonymous]

Mein Ansatz war, dass kein Kreis beim Geschenkelager und der Verpackungsstation enden darf, wenn man beide in einem Kreis hat. Man müsste sonst nämlich aufladen und dann 55 Minuten warten bis man die nächste Runde des Kreises starten darf. Aufladen sollte man auch nur bei solchen Stationen bei denen mindestens eine Zeitspanne von 5 min zwischen Ankunft und Abfahrt liegt, denn ob man einfach nur wartet (die Rentiere also Zeit für einen Glühwein hatten) oder ob man beim warten auflädt kostet keine Extrazeit.
Dann hab ich mit diesen Vorgaben ein wenig rumprobiert und bin zu folgender Lösung gelangt.

Ich habe für 7 Schlitten folgende Kreise:

Kreis a: Fahrten 5, 6 ,7 und 8 (3 Schlitten)

Kreis b: Fahrten 2, 3, 4 (3 Schlitten)

Kreis c: Fahrt 1 (1 Schlitten)

[Anonymous]

Ich brauche auch 7 Schlitten. Damit gibt es aber mehrere Möglichkeiten. Z. B. auch 4 Schlitten für die Runde (1,2,3,4) und 3 Schlitten (5,6,7,8).
Ausser brute force hatte ich aber keine Idee, wie ich zeigen kann, dass es nicht mit weniger als 7 Schlitten geht. Hat jemand eine Idee?

[Anonymous]

Hi MatheJuergen,
ich habe auch keinen schnelleren Weg gefunden. Hier meine Gedanken:
Zunächst überlegen wir uns wie die Fahrzeit mindestens sein muss (da ja die Schneemobile auf Kreisen fahren müssen).
Wir starten mit den Strecken wie sie bezeichnet sind:
20+20+35+35+15+15+20+20+20+20+20+20+30+30=320 [Minuten]
Es sind immer Hin- und Rückfahrt in der Rechnung enthalten, da die Schneemobile auf Kreisen fahren und die Kreise nur so anzuordnen sind, dass diese Fahrzeiten mindestens benötigt werden.
Da die Schneemobile zwischendurch auftanken müssen, werden in jedem Fall nochmal 320/50∙5=6.4∙5=32 [Minuten] zusätzlich benötigt. Damit folgt, dass mindestens 352 Minuten benötigt werden. Das entspräche 6 Schneemobilen. Einen solchen Weg habe ich nicht gefunden, wohl aber einen mit 7 Schneemobilen

[Anonymous]

7 ist optimal. Wenn man sich anguckt, wo 20 nach jeder vollen Stunde ein Mobil sein muss, sieht man, dass sie an folgenden Stellen sein müssen:
– zwischen Zimtlager und Schokoladenfabrik
– zwischen Schokoladenfabrik und zentralem Geschenkelager
– zwischen Verpackungsstation und zentralem Geschenklager
– zwischen Nordpolmühle und Pfefferfabrik

Zusätzlich muss ein Schlitten in 15 Minuten am Kakaospeicher sein, und einer in 30 Minuten am Zimtlager, keiner der vorherigen Schlitten kann das erreichen.

Einen letzten Schlitten muss es geben, da um 55 bzw. 0 zwei verschiedene Schlitten bei der Verpackungsstation gewesen sein müssen. Einer von diesen kann derjenige auf dem Weg zum zentralen Geschenklager sein, der andere kann keiner der oben genannten sein, da er mit Pausenzeit gerade so zu weit weg ist.

Insgesamt finde ich diesen Beweis schon nett, es ist ein einfach nachzuvollziehendes Zertifikat, und mit dieser Betrachtung kann man relativ leicht die vorhandenen Mobile zu Kreisen verknüpfen.

[Anonymous]

Ich habe eine Lösung mit nur einem Kreis in 345 Minuten = 6 Schlitten
((‘C’, ‘B’), (‘B’, ‘D’), (‘D’, ‘A’), (‘A’, ‘D’), (‘D’, ‘B’), (‘B’, ‘C’), (‘C’, ‘E’), (‘E’, ‘G’), (‘G’, ‘F’), (‘F’, ‘D’), (‘D’, ‘F’), (‘F’, ‘G’), (‘G’, ‘E’), (‘E’, ‘C’))
Wo liegt mein Fehler?

[Anonymous]

Wenn du mir sagst, was deine Buchstaben jeweils bedeuten (also welche Stationen), dann kann ich dir vielleicht helfen deinen Fehler zu finden.

[Anonymous]

Anonymous wrote:

Insgesamt finde ich diesen Beweis schon nett, es ist ein einfach nachzuvollziehendes Zertifikat, und mit dieser Betrachtung kann man relativ leicht die vorhandenen Mobile zu Kreisen verknüpfen.

Oh ja, sehr schön! Ich hatte mich gefragt (wie andere auch), wie man das am besten in den Griff bekommt. Danke!

[Anonymous]

Anonymous wrote:

Ich habe eine Lösung mit nur einem Kreis in 345 Minuten = 6 Schlitten
((‘C’, ‘B’), (‘B’, ‘D’), (‘D’, ‘A’), (‘A’, ‘D’), (‘D’, ‘B’), (‘B’, ‘C’), (‘C’, ‘E’), (‘E’, ‘G’), (‘G’, ‘F’), (‘F’, ‘D’), (‘D’, ‘F’), (‘F’, ‘G’), (‘G’, ‘E’), (‘E’, ‘C’))
Wo liegt mein Fehler?

Wenn du die Punkte von links nach rechts und von oben nach unten gewählt hast (A=Kakaospeicher, B=Zentrallager, … , G=Verpackungsstation), dann benötigst du für die gesamte Strecke mindestens 320 Minuten + 35 Minuten Pause => 355 Minuten. Da sind aber noch keine zusätzlichen Wartezeiten enthalten (z.B. zwischen Ankunft in E (ausgehend von C) und Abfahrt von E (Richtung G) ist eine 10-Minuten-Pause und nicht nur 5. An anderen Stellen ist die Wartezeit noch größer. Daher kommst du nicht mit 6 Schlitten aus.

[Anonymous]

Ahh, ein Licht geht auf. Jetzt habe ich die Aufgabe verstanden…
Die Fahrten (1) bis (8) finden zu den angegebene Zeiten statt. Das hatte ich nicht berücksichtigt.

…muss mein Programm also nochmal umstricken.

[Anonymous]

Wenn mein Programm korrekt ist, gibt es

180 Möglichkeiten, es mit 14 Mobilen zu schaffen,
3132 Möglichkeiten, es mit 13 Mobilen zu schaffen,
10644 Möglichkeiten, es mit 12 Mobilen zu schaffen,
14118 Möglichkeiten, es mit 11 Mobilen zu schaffen,
9204 Möglichkeiten, es mit 10 Mobilen zu schaffen,
2700 Möglichkeiten, es mit 9 Mobilen zu schaffen,
324 Möglichkeiten, es mit 8 Mobilen zu schaffen,
18 Möglichkeiten, es mit 7 Mobilen zu schaffen.

Hier wurden natürlich nur die 40320 Möglichkeiten betrachtet, die 8 Linien in irgendeiner sinnvollen Reihenfolge abzuarbeiten. “Sinnlose” Fahrten tauchen nicht auf.

Die 18 Möglichkeiten mit 7 Schneemobilen sind folgende (Ihr könnt ja schauen, ob euer Favorit dabei ist):

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’], 2, 120], [[‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’], 1, 40], [[‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’], 3, 165]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’], 2, 120], [[‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’], 4, 220]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’], 3, 165], [[‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’], 3, 165]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’], 6, 340]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’], 5, 300], [[‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’], 1, 40]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’], 6, 360]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’], 6, 345]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’], 1, 40], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’], 3, 160], [[‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 3, 160]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Zimtlager’, ‘Schokoladenfabrik’], 4, 225], [[‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’], 3, 165]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Zimtlager’, ‘Schokoladenfabrik’], 7, 405]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 7, 400]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 4, 220], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’], 3, 160]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Zimtlager’, ‘Schokoladenfabrik’], 7, 405]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Zimtlager’, ‘Schokoladenfabrik’], 4, 225], [[‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 3, 160]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 4, 220], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’], 2, 120], [[‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’], 1, 40]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 5, 280], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’], 2, 120]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 4, 220], [[‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’], 3, 165]]

Anzahl Schneemobile: 7
[[[‘Kakaospeicher’, ‘Schokoladenfabrik’, ‘Zentrales Geschenkelager’, ‘Verpackungsstation’, ‘Pfefferkuchenfabrik’, ‘Zimtlager’, ‘Schokoladenfabrik’, ‘Zimtlager’, ‘Nordpohlmühle’, ‘Pfefferkuchenfabrik’, ‘Verpackungsstation’, ‘Zentrales Geschenkelager’, ‘Schokoladenfabrik’], 7, 400]]

[Anonymous]

Ich hätte definitiv Interesse, mir anzusehen, wie der Quellcode speziell zu der Aufgabe konkret aussieht

[Anonymous]

Ich denke, ich könnte eventuell doch noch eine Lösung mit 6 Schneemobilen gefunden haben. Ich habe zumindest in der Aufgabenstellung keine Widersprüche zu meiner Lösung gefunden. Hier ist der Link, auf dem ich meine Lösung zusammengefasst habe:
https://1drv.ms/b/s!Aps2c4mdhSuywCC4iO0JvEHyqiPf?e=YAaHeQ

[Anonymous]

Stimmt! Bin begeistert! Das müsste sich das Team auch noch einmal anschauen!👍🏻

[Anonymous]

@Jonah: Deine Lösung finde ich zwar schön, aber ich denke doch, dass die Idee Tour (1) und (2) zusammenzufassen, der Aufgabe widerspricht. Du müsstest dann zwischen Kakaolager und Schokoladenfabrik beide Schlittenladungen mit demselben Schlitten transportieren.

[Anonymous]

Anonymous wrote:

Ich denke, ich könnte eventuell doch noch eine Lösung mit 6 Schneemobilen gefunden haben. Ich habe zumindest in der Aufgabenstellung keine Widersprüche zu meiner Lösung gefunden. Hier ist der Link, auf dem ich meine Lösung zusammengefasst habe:

Deine Lösung ist leider falsch: Die Richtung der Route (2) ist laut Aufgabenstellung umgekehrt, also vom Zimtlager zur Schokoladenfabrik.

[Author]

Posts