nicht angemeldet
Salam!
Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!
In der Aufgabenstellung steht nix von nummerierten Säckchen, deswegen kannst du die 10! auch weglassen. Und selbst wenn würde man als erstes in einer allgemeinen Lösung o.B.d.A fordern das die Säckchen aufsteigend nummeriert werden, um solche Isomorphien auszuschließen.
Das hätte auch den Vorteil dass du alle 122 offensichtliche Lösungen nennen könntest, statt dich auf die 115 mit 10! Permutationen zu beschränken (die anderen 7 haben doppelte Säcke sodass man nur noch 10!/2 Permutationen hätte).
Ich möchte mal eine Annahme über den kompletten Lösungsraum anstellen:
Seien die Säcke aufsteigend durchnummeriert, d.h mit s_i Anzahl der Münzen im Sack i gelte s_i =< s_{i+1} für i aus {1,..,9}.
Annahme: Eine aufsteigende Zahlenfolge (s_1,..s_10)
mit S_i= s_1 + ... + s_i = Summe { s_j | j<i }
ist genau dann eine Lösung wenn gilt:
a) s_1 = 1
b) s_i =< 1 + S_{i-1} für i={2,..,10}
c) s_10 = 500 - S_9
d) S_10 = 500
insbesondere gilt s_10 =< 250!
Beispiel:
(1, 2, 4, 6, 10, 16, 33, 65, 129, 234)
s_1=2 =< 1+1=2
s_2=4 =< 1+1+2=4
s_3=6 =< 1+1+2+4=8
s_4=10 ist > 2^3 und <= 1+1+2+4+6=13
usw.
Beweis: vollständige Induktion:
Man zeigt einfach sukzessive für n =1 bis 10 dass für die Teilfolgen (s_1,..s_n) gilt, dass sich alle Zahlen kleinergleich S_n durch Addition aus Teilfolgenelementen darstellen lassen.
Für die Zahlen kleinergleich S_{n-1} brauchen wir das nicht zu zeigen, das folgt unmittelbar aus dem vorhergehenden Induktionsschritt. Und für alle Zahlen x im Intervall S_{n-1} bis S_n gilt wg. Bedingung b) unmittelbar dass x - s_n =< S_{n-1} womit wir eine Summendarstellung erhalten.
Für die Rückrichtung, dass es keine weiteren Lösungen gibt, muss man sich überlegen das mit
b*) s_i > 1 + S_{i-1}
Folgen würde das 1 + S_{i-1} schon nicht mehr darstellbar wäre.
Und d) s_10 =< 250 gleichbedeutend mit S_9 >= 250
q.e.d.
bekomme ich jetzt 500€?
:) Ashanti
Der Martin