Kombinatorik: Verteilung von 100 Goldstücken unter 4 Leuten mit Berücksichtigung des Rangs

Question

Hallo :)

Ich kann irgendwie diese Aufgabe nicht lösen :

c) Kapitän Morgan will 100 Goldstücke verteilen zwischen sich, seinem ersten Steuermann, seinem zweiten Steuermann und dem Mast. Randbedingung ist, dass in dieser Hierarchie ein höher Stehender immer mindestens so viel bekommen muss, wie die Nachgeordneten und keiner leer ausgehen darf. Wie viele Verteilungen sind möglich?
 

Mein Ansatz:

- es ist eine surjektive Abbildung von N nach R (N - Goldstücke, R - Kapitan, Steuermänner und Maat). Jeder der Männer bekommt mindestens ein Goldstück und keiner darf leer auskommen

- N ist nicht unterscheidbar, R ist unterscheidbar ( bin hier nicht sicher)

Ich weiß jetzt nicht wie ich diese Hierarchie einbeziehen soll.

Kann mir irgendjemand helfen? Wäre sehr dankbar dafür :)

Grüß :)

Comments

Das mit der Hierarchie ist mir auch noch nicht klar. Damit keiner leer ausgeht, kannst du einfach jedem 1 Goldstück geben und dann noch 96 Goldstücke verteilen.

---

Die Partitionsfunktion ist dafür gedacht eine Zahl in Summanden zu unterteilen. Grundsätzlich erlaubt die Partitionsfunktion die Unterteilung in beliebig viele Summanden. Hier betrachtet man daher nur einen Teil der Partitionsfunktion, die es erlaubt eine Zahl in eine bestimmte Anzahl an Summanden zu unterteilen.

https://de.wikipedia.org/wiki/Partitionsfunktion

Wir wollen hier die Zahl 100 in 4 Summanden (ohne Betrachtung der Reihenfolge) unterteilen.

Damit lautet die Partitionsfunktion P(100, 4)

Bei Wikipedia ist auch ein kleiner rekursiver Algorithmus gegeben. Es scheint wohl keine Möglichkeit zu geben das Formelmäßig zu lösen.

Ich habe das ganze mal in JAVA probiert

public int part(int n, int k) {       
if ((k == n) || (k == 1)) return 1;       
if ((n < k) || (k == 0)) return 0;        
return part(n - k, k) + part(n-1, k-1); }

Das liefert auch 7153 Möglichkeiten.

---

Dieser Thread ist zwar schon etwas älter, aber wie würde der programmatische Ansatz sein, wenn die Randbedingung lautet, dass in dieser Hierarchie ein höher Stehender immer mehr bekommen muss (also NICHT mindestens soviel), wie die Nachgeordneten und keiner leer ausgehen darf. Wie viele Verteilungen sind möglich?

Danke.

Answer 1

Mit einem kleinen VBA-Programm komme ich auf 7153 Möglichkeiten:

Sub GoldStueckeFuer4SchiffsLeute()
Anzahl = 0
For p = 4 To 100 Step 4        ' Mast
   For q = 0 To 96 Step 3       ' 2. Steuermann
       For r = 0 To 96 Step 2    ' 1. Steuermann
           For s = 0 To 96           ' Kapitän
              If s + r + q + p = 100 Then Anzahl = Anzahl + 1
           Next
       Next
    Next
Next
MsgBox Anzahl
'Resultat = 7153
End Sub

Comments

Hm. Ich muss gestehen, das ich durch das Programm nicht durchsteige. 

Was macht dort die Step anweisung? Bedeutet es das die For Schleife in bestimmten Schritten hochzählt?

For p = 4 To 100 Step 4        ' Mast

Bedeutet es das die Anzahl der Münzen für den Mast 4, 8, 12, ... sein kann? Warum nicht 5, 6, ...

Wie wird hier sichergestellt, das ein höherer Rang, mind. soviele Münzen bekommt wie der Rang unter ihm?

Also dein Programm scheint ja richtig zu sein. Immerhin kommt auch das heraus was ich raus habe. Allerdings verstehe ich das Programm nicht wirklich :(

Wäre nett, wenn Du mir vielleicht auf die Sprünge helfen könntest.

---

Da die Leute mit einem höheren Rang mindestens so viel wie der jeweils unter ihm Stehende erhalten sollen, war meine Idee, man gibt dem Untersten immer gleich 4er-Pakete. Davon gibt er von jedem Paket ein Goldstück jedem Höheren. Dem Nächsten gibt man 3er-Pakete, davon gibt er den 2 Höheren je Paket ein Goldstück, usw. Der Kapitän bekommt dann noch den Rest.

STEP 4 bewirkt, dass die Schleife in 4-er-Schritten durchgeführt wird.

---

Oh danke. Jetzt kapier ich die Gedankengänge :)