Lösungsdiskussion

[Noname_MM]

Hallo zusammen,

Da die Abgabe für Aufgabe 1 jetzt abgeschlossen ist, dürfen wir hier doch sicherlich unsere Lösungsvorschläge austauschen? (Wenn nicht: Sorry liebe Moderatoren!)

Meine Lösung ist Nr. 8, als 75.
Kurze Erklärung: Per Gaußscher Summenformel den Gesamtwert der Münzen errechnet und durch 3 geteilt. Das ist das Minimum, was unsere gute Elfe immer erreichen kann, da sie ja die Truhe am Ende aussuchen darf und immer die wertvollste Truhe nehmen wird. Also muss die Gegenseite versuchen möglichst gleichzuverteilen, was ihr vermutlich gelingt. (Da ist mein Schwachpunkt - ich habs nicht so mit bester Strategie. Vielleicht gibt es eine bessere Strategie für die Elfe?)

[st1974]

Ich habe Antwort 3: Endziffern 25.
Die optimale Strategie ist nämlich die, eine Gleichverteilung bis zum vorletzten Zug zu erzwingen, ohne die Münze 2025 zu verwenden. Dann befinden sich in jeder Truhe Münzen im Wert von 683100. Als letztes legt Johanna dann die Münze 2025 in die ausgewählte Truhe und erhält so Münzen im Wert von 685125.
Ein Abweichen von dieser Strategie ist für keine der beiden Seiten von Vorteil. Sollte Johanna irgendwann im Spiel eine Truhe mit mehr als 683100, aber weniger als 685125 haben, dann würde die Bank diese Truhe nicht mehr auswählen und es gäbe nach dem vorletzten Zug eine Truhe mit weniger als 683100, in die dann die 2025er Münze gelegt werden müsste. Andererseits, würde die Bank im Laufe des Spiels eine Truhe mit genau 683100 auswählen, dann könnte Johanna bereits in diesem Zug die 2025er Münze hineinlegen, um so das Optimum zu erhalten.
Man müsste lediglich noch beweisen, dass sich diese Gleichverteilung tatsächlich immer erzwingen lässt, was aber intuitiv möglich sein sollte, wenn immer die größtmögliche Münze aus 1 - 2024 genommen wird, ohne den Wert von 683100 zu übersteigen.

[Mathewichtel]

Das war auch eine meiner Ideen - ich bin mir aber nicht sicher, ob das klappt:
Ich fürchte (kann es aber nicht vernünftig begründen), dass die Bank dieses System sabotieren kann. 
Die Bank möchte ja keine Gleichverteilung der Münzen von 1 bis 2024, sondern von allen Münzen. Wenn in einer Truhe der Füllstand noch etwas unter 683.100 Münzen ist, könnte die Bank doch diese Truhe erstmal nicht mehr auswählen und Johanna am Ende zwingen, die 2025er-Münze dort hineinzulegen, so dass diese Truhe dann zwar vielleicht am Vollsten ist, aber eben nicht ganz bei 685.125 Münzen.
Weiter bin ich mit meinen Überlegungen leider nicht gekommen, Optimierungsstrategien sind nicht so meine Stärke…
Was meinen die anderen?

[Abraxas]

Ich habe auch Lösung 3, Endziffern 25, selbe Strategie.

Eine Gleichverteilung lässt sich z.B. so erzwingen:

Jeder Truhe werden feste Münzwerte zugeordnet, die jeweils den Wert 683100 ergeben. Das geht z.B. so:

Man lässt die beiden Münzen 1 und 2 vorerst beiseite und bildet mit den restlichen Münzen mit Wert 3 bis 2024 Paare, die jeweils die Summe 2027 haben:

3+2024=2027
4+2023=2027
…
1013+1014=2027

Das sind insgesamt 1011 Paare. Je 337 dieser Paare werden jeder Truhe zugeordnet, also jeweils ein Wert von 683099. 

Nun wird zu Truhe 1 zusätzlich noch die Münze 1 zugeordnet, also insgesamt 683100.

Von den Truhe 2 und 3 zugeordneten Münzen werden zwei mit nebeneinander liegenden Werten getauscht, also z.B. Münze 4 von Truhe 2 mit Münze 5 von Truhe 3. Somit sind zu Truhe 2 nun Münzen im Wert von 683100 zugerechnet und zu Truhe 3 Münzen im Wert von 683098. Zu Truhe 3 wird nun zusätzlich noch die Münze 2 zugeordnet, also auch hier Wert 683100.

Je nachdem, in welche Truhe dann jeweils eine Münze gelegt werden soll, wählt man eine der zugeordneten aus.

[Kosakenzipfel]

Wie erzwingen ich gleich Verteilung. Ich dachte mir, die Bank zeigt immer auf die Truhe mit dem momentan kleinsten Inhalt (was anderes wäre vermutlich für die Bank nicht optimal). Und dann legt Johanna da ihre kleinste Münze rein. Dann wäre 6) die richtige Antwort.

[Raaadi]

Was ein Aufwand für den geringen Mehr-Verdienst...    Ich hatte als eine Strategie, die (garantiert) nicht bei "T1 = 1/3, T2 = 1/3, T3 = 1/3" landet: Wenn Truhe1 gewählt wird, dann packe da die höchste verfügbare Münze rein. Wenn Truhe2 gewählt wird, dann packe dort die niedrigste verfügbare "ungerade" Münze rein, wenn Truhe 2 gewählt wird, dann packe dort die niedrigste verfügbare "gerade" Münze rein. Am Ende trifft's sich bei Runde 2025 an der 1654-Münze. Aber egal, wo die reinkäme, ich komme nicht auf eine der Endziffern aus der Lösung! Demnach gibt es also eine bessere Strategie, wobei ich persönlich mich mit 683.775 zufrieden geben würde.

[hg1]

Ich habe eine ähnliche Strategie für die Elfe wie Abraxa, um auf 685125 zu kommen. Vielleicht als Ergänzung für die Optimalität: Indem die Bank immer die aktuell kleinste Truhe auswählt, kann sie garantieren, dass zu jedem Zeitpunkt der Abstand zwischen der kleinsten und der größten Truhe höchstens 2025 ist. Unter dieser Bedingung ist die 683100 + 683100 + 685125 die Aufteilung mit dem größten Maximum, d.h. die Bank kann sicherstellen dass die Elfe nicht mehr als 685125 bekommt.

[Mathewichtel]

Ich bin immer noch nicht überzeugt, lasse mich aber gerne eines besseren belehren, da ich es mit den selben Argumenten versucht habe und leider den Knoten im Hirn nicht aufgelöst bekomme.
Das Ziel der Bank muss doch eine Gleichverteilung ALLER Münzen sein, also pro Truhe 683775. Kann die Bank dann nicht, wenn eine der Truhen 683775-2025 Münzen enthält, diese Truhe erstmal auslassen und die Elfe zwingen, die anderen beiden Truhen bis 683775 aufzufüllen? Die vorher ausgesparte Truhe käme dann erst als letztes wieder dran, und alle Truhen wären gleichmäßig gefüllt.
Wo ist mein Denkfehler?

[hg1]

Ich bin immer noch nicht überzeugt, lasse mich aber gerne eines besseren belehren, da ich es mit den selben Argumenten versucht habe und leider den Knoten im Hirn nicht aufgelöst bekomme.
Das Ziel der Bank muss doch eine Gleichverteilung ALLER Münzen sein, also pro Truhe 683775. Kann die Bank dann nicht, wenn eine der Truhen 683775-2025 Münzen enthält, diese Truhe erstmal auslassen und die Elfe zwingen, die anderen beiden Truhen bis 683775 aufzufüllen? Die vorher ausgesparte Truhe käme dann erst als letztes wieder dran, und alle Truhen wären gleichmäßig gefüllt.
Wo ist mein Denkfehler?

Ich denke das Problem dabei ist, dass die Bank die Elfe nicht zwingen kann die Truhen bis 683775 aufzufüllen. Sondern die Elfe füllt (durch passende Wahl der Münzen) die Truhen nur bis 683100 auf, und wenn die Bank eine Truhe danach dann nochmal auswählt kommt packt sie die 2025-Münze dazu -> gesamt 685125

[WolfgangR]

Ich habe auch Lösung 3. Es gibt eine analoge Aufgabe mit 2 Truhe aus dem Bundeswettbewerb Mathematik 2020 Runde 2 Aufgabe 1. In der Musterlösung BWM_2020_R2_A1 ist die Strategie sehr gut beschrieben und kann leicht auf diese Aufgabe angewendet werden.