Forum: Wissenschaft
Rätsel der Woche: Teile und herrsche
SPIEGEL ONLINE

Der Reichtum eines Königs wird neu verteilt, er selbst und neun Untertanen teilen sich jeden Montag zehn Taler. Der Verteilungsschlüssel darf verändert werden, sofern es eine Mehrheit dafür gibt. Wie taktiert der Monarch am geschicktesten?

Seite 3 von 4
permissiveactionlink 05.12.2017, 11:37
20. In der Aufgabe

wird nirgendwo explizit verlangt, dass die Münzen glatt auf eine Anzahl von Bürgern zu verteilen sind. Es ist also durchaus möglich, dass der König in seinem ersten Vorschlag die Verteilung von 6 Talern auf 5 Bürger abstimmen lässt. Jeder dieser Bürger hat nun 20% mehr als vorher, wird also zustimmen. Abstimmungsergebnis 5 :4. Der König sackt zusätzliche drei Täler ein. Im nächsten Schritt werden 4 Taler auf 3 Bürger verteilt. Für diese steigt das Einkommen nochmals um 11,11%. Abstimmergebnis 3 : 2 dafür. Der König sackt weitere 2 Taler ein. Im letzten Schritt werden 3 Taler auf 2 Bürger verteilt, die nochmals je 12,5 % mehr Einkommen erzielen. Abstimmergebnis 2 : 1. Der König kommt auf einen weiteren Taler. Insgesamt wieder 7. Auch über diesen alternativen Weg kommt der König höchstens an (n - 3) Taler. Es sind aber lediglich drei Vorschläge und Abstimmungen erforderlich. Der König selbst kann nur ganze Taler verteilen. Die Bürger aber können Taler, die nicht glatt aufgeteilt werden können, draußen umtauschen und gerecht verteilen, zur Not über Naturalien.

Beitrag melden Antworten / Zitieren
markus_rode 05.12.2017, 18:47
21. Jahresgehalt - Realistischere Alternative

Ja, lustige Lösung - aber wie ein Kommentar bemerkte: Das wird der König nicht lange überleben. Nicht einen Tag. OHNE das mehrmalige Abstimmen hatte ich einen anderen Ansatz, der dem König den Löwenanteil LANGFRISTIG sichern könnte: EIN Abstimmungsvorschlag: Talerverteilung für das ganze JAHR festlegen. Also 12 Monate. FÜNF Bürger erhalten in je EINEM Monat einen Extrataler. Vier gehen komplett leer aus. Von den 12*10 Talern gehen dann 5*13 Taler an die zufriedene Mehrheit (8% mehr - dafür streikt man anderswo!). Null an die Minderheit. 55 an den König. Gut genug. - Mathematisch "optimieren" ließe sich das zwar bei längerer Regelung (Pro Jahrtausend einen Taler mehr - der Anteil des Königs nähert sich max. 60 Talern pro Jahr.) Aber bei sowenig Vorteil ließen sich die 5 kaum mehr für die Enteignung der 4 gewinnen. Auch game-theory ist Mathematik, oder? ;)

Beitrag melden Antworten / Zitieren
emil_erpel8 05.12.2017, 19:01
22.

Zitat von WernerGg
Jetzt ist guter Rat teuer. Wie könnte man wohl eine optimale Lösung finden? Optimal im Sinne von maximalen Ertrag für den König am Schluss und/oder minimaler Anzahl Verteilungsschritte.
Nö, guter Rat ist hier ganz billig zu haben:

1. Bei mindestens fünf Untertanen:

Die Anzahl der Untertanen (U) mit Einkommen kann in jedem Schritt fast halbiert werden, indem man gerade einem Untertanen weniger alles wegnimmt. Das Geld wird gleichmäßig auf die Untertanen verteilt, die noch Einkommen besitzen.

Dieses Verfahren endet, wenn nur noch zwei Untertanen Einkommen besitzen. Im letzten Schritt nimmt der König diesen beiden ihr gesamtes Einkommen, gibt drei bisher Einkommenslosen je einen Taler und den Rest dem König.

Die Anzahl der nötigen Schritte beträgt

[log2(U-1)] + 1

Wobei [...] hier die obere Gaußklammer bezeichne.

Am Schluß hat der König per Konstruktion des Verfahrens ein Einkommen von U-2 Talern, was, wie hier bereits bewiesen wurde, nicht zu überbieten ist.

Ebenso sollte leicht einzusehen sein, daß

a) die Anzahl der Untertanen ohne Einkommen nicht noch schneller erhöht werden kann (solche Vorschläge fänden keine Mehrheit),

b) das Maximum des königlichen Einkommens genau dann zu erzielen ist, wenn vor dem letzten letzten Schritt das gesamte Einkommen genau zwei Personen weggenommen wird (wären es mehr, müßte sich der König die Zustimmung von mehr als drei Untertanen erkaufen).


2. Bei vier Untertanen oder weniger kann der König nicht über den einen Taler Einkommen hinauskommen.

Beweis: Übung

Beitrag melden Antworten / Zitieren
emil_erpel8 05.12.2017, 19:08
23.

Zitat von WernerGg
Im Prinzip ist klar, dass man das als Spiel auffassen kann, das auf eine mehr oder weniger intelligente Baumsuche hinausläuft mit den Spielzuständen (Taler pro Bürger und König) als Knoten und den daraus möglichen Verteilungen auf Grund der Regeln als Kanten je Knoten zu den Folgezuständen. ... Da denkt man dann an Subsets, IntegerPartitions, Permutationen, Gruppen und dergleichen. Das ist nicht trivial und nicht in ein paar Tagen erledigt.
Also, wenn man das leicht beweisbare optimale Verfahren gerne ignorieren und es sich künstlich kompliziert machen will, nur zu. Wann ist mit Ergebnissen über die mögliche Anzahl "Spielverläufe" in Abhängigkeit von N zu rechnen?

Beitrag melden Antworten / Zitieren
ManeGarrincha 05.12.2017, 21:57
24. Ich sehe das genau so

Zitat von DerDifferenzierteBlick
Das hätte man noch mal explizit dazuschreiben sollen, damit keine Unklarheiten entstehen. Ansonsten ganz nett, allerdings kann man durch probieren recht schnell zum Ergebnis kommen.
Es ist tatsächlich sehr betrüblich, dass in diesen vermeintlich mathematischen Rätseln die Aufgabenstellung oft nur sehr bruchstückhaft formuliert wird. In der ursprünglichen Aufgabe von Peter Winkler war genau erwähnt, dass es nur um ganzzahlige Beträge und mehrmalige Abstimmungen geht.

Beitrag melden Antworten / Zitieren
nessaalk 06.12.2017, 15:03
25. ..genau lesen..

Zitat von ManeGarrincha
Es ist tatsächlich sehr betrüblich, dass in diesen vermeintlich mathematischen Rätseln die Aufgabenstellung oft nur sehr bruchstückhaft formuliert wird. In der ursprünglichen Aufgabe von Peter Winkler war genau erwähnt, dass es nur um ganzzahlige Beträge und mehrmalige Abstimmungen geht.
Übrigens: Es ist in der Aufgabe von "Vorschlägen" die Rede, die der König machen kann, also mehrere Vorschläge. Das deutet doch auf mehrere Schritte hin. Und das Aufteilen der Taler in Cent, Kreuzer oder was auch immer ändert nichts an der Lösung (n Taler - 3 x), wobei n die Zahl der Taler und x die kleinste verfügbare Geldeinheit ist.
Warum soll man eigentlich immer alles haarklein im Rätsel vorkauen? Es ist doch ein Rätsel und keine Abituraufgabe.
(Und wenn man nach einem Schritt keinen Gewinn für den König sieht, ist es doch ein netter Aha-Effekt, dass er zunächst etwas investieren muss, um dann königlich abzusahnen.)

Beitrag melden Antworten / Zitieren
WernerGg 06.12.2017, 15:49
26. @emil_erpel8 - Baumsuche

Zitat von emil_erpel8
Also, wenn man das leicht beweisbare optimale Verfahren gerne ignorieren und es sich künstlich kompliziert machen will, nur zu. Wann ist mit Ergebnissen über die mögliche Anzahl "Spielverläufe" in Abhängigkeit von N zu rechnen?
Ich sagte schon, dass ich mir das lieber nicht antue. Erstens, weil ich nicht weiß, wie man alle Züge pro Zustand halbwegs effizient aufzählen kann. Zweitens weil das sehr rechenintensiv wird. Drittens weil es nichts bringt.

Ich bin inzwischen auch davon überzeugt, dass der König nicht mehr als n-3 Taler machen kann, wie man alleine aus der Betrachtung des letzten Zugs sieht und hier mehrfach vorgeführt wurde. Die Vorgeschichte spielt dafür gar keine Rolle.

Beitrag melden Antworten / Zitieren
emil_erpel8 06.12.2017, 17:33
27.

Zitat von nessaalk
Warum soll man eigentlich immer alles haarklein im Rätsel vorkauen? Es ist doch ein Rätsel und keine Abituraufgabe.
Heutzutage ist es eben so, daß immer wer anderes schuld sein muß, wenn man's selbst nicht rausgekriegt hat (so wie ich dieses mal nicht darauf kam, daß der König auf sein Einkommen verzichten kann, um den Prozeß in Gang zu setzen).

Beitrag melden Antworten / Zitieren
brandeco 10.12.2017, 06:18
28. Aufgabe nicht vollständig

Dass weitere Abstimmungen möglich sind, bei denen die vorher Überstimmten keine Stimme mehr haben, hätte gesagt werden müssen. So musste man davon ausgehen, dass bei jeder Abstimmung wiederum alle das gleiche Stimmrecht haben.

Beitrag melden Antworten / Zitieren
AlaskaSaedelaere 10.12.2017, 13:07
29.

Zitat von brandeco
Dass weitere Abstimmungen möglich sind, bei denen die vorher Überstimmten keine Stimme mehr haben, hätte gesagt werden müssen. So musste man davon ausgehen, dass bei jeder Abstimmung wiederum alle das gleiche Stimmrecht haben.
Wie kommen Sie darauf, daß die Überstimmten keine Stimme mehr haben? Jeder der Untertanen hat und behält sein Stimmrecht. Es ist sogar genau angegeben, wie er abstimmt.

Beitrag melden Antworten / Zitieren
Seite 3 von 4