Rätsel für Stochastiker

ErzEngel · Moderator Anmeldedatum: 03.06.2001 Beiträge: 2794 Wohnort: Nähe Altötting

Cool, vielleicht bekomm ich noch einen Kommilitonen von mir dazu, das mal unseren Mathe-Professoren vorzulegen.
Dann könnte man die gesamte Mathe-Fraktion Deutschlands irgendwann damit beschäftigen.

Ein mathematischer Virus. Ich wusste gar nicht, dass ich implizit sowas erfunden habe.

kilrah · Kämmerer Anmeldedatum: 13.11.2003 Beiträge: 691 Wohnort: Salzburg

Leicht ist das Rätsel sicher nicht - die meisten stochastischen Probleme löst man mit etwas Erfahrung schon beim ersten hinsehen. Das ist hier nicht der Fall. Aber extrem schwer sollte es auch nicht sein. Ich hab nur keine Lust mich einen Tag lang damit zu beschäftigen, so lange würd ich schätze ich mal für eine (formelle) Lösung brauchen.

MarkusProject · Moderator Anmeldedatum: 31.05.2001 Beiträge: 2033 Wohnort: Hannover / Schwerin

Ich habe es mir nicht nehmen lassen und in einem kleinen Programm Variationen etc. erstellen lassen. Man hat ja sonst nix zu tun...

Dazu habe ich einfach eine 6-6-Variation mit Wiederholungen erzeugt (also 111111; 111112 usw. bis 666666), das sind insg. 46656 Möglichkeiten. Daraus habe ich alle Möglichkeiten mit unzulässigen Anzahlen herausfiltern lassen (also mehr als eine 1 etc.) Bleiben 31321 Möglichkeiten. Der Algorithmus für das Herausfiltern der Rotationssymmertrie ist auch nicht schwer, aber leider überfordert der Vergleich von 30000 Zeichenketten mit 30000 anderen meinen Rechner sehr stark. Ich glaube, man sollte doch lieber rechnen...

Aber jetzt habe ich erstmal Ferien!!!

ErzEngel · Moderator Anmeldedatum: 03.06.2001 Beiträge: 2794 Wohnort: Nähe Altötting

Also um es nochmal genau zu sagen:
Es geht mir hierbei nicht um eine numerische Lösung, damit ich dann weiß, wieviele Möglichkeiten es gibt. Das ist nicht so schwer rauszufinden.

Es geht mir hierbei um eine arithmetische Lösung, also eine stochastische Berechnungsformel für diese Art von Problem.

Vielleicht gibt es sowas, ich glaube aber inzwischen eher, dass es so eine Formel nicht gibt.

MarkusProject · Moderator Anmeldedatum: 31.05.2001 Beiträge: 2033 Wohnort: Hannover / Schwerin

Ich weiß, wollte eigentlich auch nur mal was ausprobieren.

Auf die rechnerische Lösung kommen wir sicher auch noch...

Tinuviel · Händler Anmeldedatum: 13.08.2003 Beiträge: 216 Wohnort: Essen

...öhm, das ist mir dann doch alles zu hoch

aber ne Bekannte von mir studiert Mathematik... hmm

Scherge · Händler Anmeldedatum: 25.09.2001 Beiträge: 154 Wohnort: Dresden

Hmmm. Das ist eines dieser interessanten, einfach anmutenden aber doch enorm schweren kombinatorischen Probleme.
Aufgaben dieser Art werden häufig bei der Internationalen Mathematikolympiade gestellt, und diese hier könnte eine der schwereren Art sein, es sei denn ich habe die einfache Lösung bisher übersehen.
Viele kombinatorische Probleme sind heute noch un- oder nur teilweise gelöst, z.B. das Problem der Ramsey-Zahlen: http://en.wikipedia.org/wiki/Ramsey_number
Mit solchen Problemen haben sich die besten Mathematiker schon beschäftigt, und es gibt einige Zahlenfolgen, die daraus resultiert sind: Die Stirling-Zahlen erster und zweiter Art, die Catalanschen Zahlen, die Bellschen Zahlen usw.

Ein Ziel wäre jetzt, so eine Zahlenfolge aufzustellen. D.h. man beginnt mit einem Plättchen "1", dafür gibt es offensichtlich genau eine Möglichkeit. Dann mit 1x"1" und 2x"2", da sind es zwei Möglichkeiten. Und man versucht den allgemeinen Fall irgendwie auf bekannte Formeln oder die vorigen Fälle (mit weniger Plättchen) zurückzuführen, um damit eine explizite oder wenigstens rekursive Berechnungsvorschrift zu gewinnen.
Das ist hier sicher auch möglich, aber sehr kompliziert.

Tja, leider ist mir das nicht gelungen. Das Problem ist schließlich ziemlich komplex: Erstens die Auswahl von 6 Plättchen aus 21, zweitens sind manche von denen nicht unterscheidbar, und drittens kommt dann noch die Symmetrie hinzu. Für alle diese drei Probleme gibt es Formeln, aber hier muss man die irgendwie kompliziert verknüpfen, oder aber viele Fallunterscheidungen machen.

Mir ist es nicht gelungen, irgendeine Formel zu entwickeln, und ich werde das auch nicht weiterverfolgen, weil ich kaum glaube, dass ich da in annehmbarer Zeit Erfolg haben werde. Es hat schon lange genug gedauert, die Aufgabe über systematisches Zählen zu lösen:

Am besten geeignet für eine Fallunterscheidung schien mir nach etwas Rumprobieren das Kriterium, wie viele von den 6 aus 21 Zahlen gleich sind.

1. Für den Fall, das alle sechs Plättchen gleich sind, gibt es genau eine zyklische Anordnung, sowie eine Möglichkeit der Auswahl, nämlich genau 6x"6". Also haben wir hier 1 Anordnung.
2. Fall: 5 gleiche, 1 anderes Plättchen (das schreibe ich ab jetzt in der Form "5a,1b"). Dann gibt es genau eine zyklische Anordnung baaaaa. Für b kommen "5" und "6" in Frage, für a alle anderen. Somit gibt es 2*5*1=10 Möglichkeiten.
3. Fall: 4a,2b. Anordnungen aabbbb, ababbb und abbabb, Auswahlmöglichkeiten a=4/5/6, b aus 2-6 ohne a. Also 3*4*3 = 36 Möglichkeiten.
4. Fall: 4a,1b,1c. Anordnungen baaaac, baaaca, baacaa, bacaaa, bcaaaa (5). 3 Möglichkeiten für a, sowie (5 über 2) = 10 für b und c. Macht 3*10*5 = 150.
5. Fall: 3a,3b. Anordnungen aaabbb, aababb, aabbab, ababab (4). (4 über 2)=6 Möglichkeiten für a und b. Macht 6*4 = 24.
6. Fall: 3a,2b,1c. Wir setzen c an irgendeine fest gewählte Position, die anderen 5 Plättchen können wir dann frei verteilen - alle solchen Verteilungen sind verschieden, denn wenn man zwei durch Rotation ineinander überführen könnte, läge c dann an anderer Stelle, was unmöglich ist, weil es nur ein c gibt. So verfahren wir jetzt immer, wenn möglich. Für die 3a und 2b gibt es dann 5!/(2!*3!) = 10 Möglichkeiten (Formel für die Permutation mit Gruppen). a können wir aus 3/4/5/6 wählen (4), b aus 2-6 ohne a (4), c aus 1-6 ohne a und b (4). Also 4*4*4*10 = 640 Anordnungen.
7. Fall: 3a,1b,1c,1d. Setze d an feste Stelle, permutiere die anderen Plättchen: 5!/3! = 20 Möglichkeiten. a kann man aus 4 Zahlen auswählen, für b-d gibt es (5 über 3) = 10 Möglichkeiten. Also insgesamt 4*10*20 = 800 Anordnungen.
8. Fall: 2a,2b,2c. 16 Anordnungen: aabbcc, aabcbc, aaccbb, aacbbc, aabccb, aacbcb, ababcc, abacbc, abaccb, acabbc, acabcb, acacbb, abbacc, abcacb, abcabc, acbacb. (5 über 3) = 10 Möglichkeiten der Auswahl, insgesamt 16*10 = 160.
9. Fall: 2a,2b,1c,1d. 5!/(2!*2!) = 30 Möglichkeiten der zyklischen Anordnung, (5 über 2)=10 für a und b, (5 über 2) = 10 für c und d. Macht 10*10*30 = 3000 Möglichkeiten.
10. Fall: 2a,1b,1c,1d,1e. 5!/2! = 60 Anordnungen, 5 Möglichkeiten für a, (5 über 4) = 5 Möglichkeiten für b-e, insgesamt 5*5*60 = 1500.
11. Fall: alle Plättchen verschieden. Dann gibt es 5! Möglichkeiten, sie anzuordnen, und genau eine Möglichkeit, sie auszuwählen, macht 1*5! = 120.

Insgesamt erhalten wir damit 6441 Möglichkeiten.

Der allgemeine Fall wäre nun: wir haben für k=1,...,n jeweils k Plättchen "k". Aus diesen wählen wir dann n Stück aus und ordnen sie auf einem Kreis an. Gesucht ist die Anzahl der Möglichkeiten dafür.
Meine Ergebnisse sind:
n=0: 1

n=1: 1
n=2: 2
n=3: 7
n=4: 46
n=5: 423
n=6: 6441
n=7: 78688
Hundert Punkte für denjenigen, der hier die Gesetzmäßigkeit findet.
Man könnte natürlich auch ein Programm schreiben, das die Zahlen ausrechnet, das sollte nicht allzu schwer sein. Aber als zukünftiger Mathematiker hab ichs natürlich auf Händen und Knien mit Bleistift und Papier gerechnet

.

Gruß,
Scherge

McSunfly · Moderator Anmeldedatum: 07.05.2001 Beiträge: 1531 Wohnort: Hürtgenwald

Moin Scherge,

Hut ab vor Deiner Herleitung. aber wenn es so "trivial" wäre, wäre es ja vielleicht noch lösbar, aber die Anordnung an sich, die "Reihenfolge" ist dem Erzi ja auch noch wichtig.

ErzEngel · Moderator Anmeldedatum: 03.06.2001 Beiträge: 2794 Wohnort: Nähe Altötting

Hi Mc,

also hier muss ich dich leider enttäuschen, da hast du es falsch verstanden. Es ist wirklich so, dass deine 60 Möglichkeiten wegen der Rotationssymmetrie (die Plättchen werden ja im Kreis angeordnet und es gibt keinen definierten Anfangspunkt, von dem man schaut) auf 10 zusammenfallen.

Daher hat Scherge mit den 10 Recht.