Question

Wie kann man die Anzahl der Möglichkeiten exakt berechnen?

Erste Frage Aufrufe: 483 Aktiv: 18.09.2023 um 21:13

Jetzt Frage stellen

0

Gegeben ist das Spielfeld:

Das Titelbild zeigt das Spiel Seemanns-Solitär. Bei diesem Spiel sollen die schwarzen und weißen Steine mit möglichst wenigen Zügen die Seiten wechseln. Jeder Stein kann auf ein leeres benachbartes Feld geruckt werden (zwei Felder sind benachbart, wenn sie eine gemeinsame Seite haben). Außerdem kann ein Stein über einen benachbarten Stein springen, wenn das Zielfeld leer ist, wobei man nicht ums Eck springen kann. Dabei ist die Farbe der Steine egal.

Aufgabe 1:
a) (0.5 Pkt):
Berechne exakt wie viele verschiedene Zustände im Seemanns-Solitär auftreten können.

Wie kann man hier vorgehen, aufgrund der Punktezahl, bei einem Blatt mit 30 Punkten, ist das wahrscheinlich extrem einfach, ich habe jedoch keinen Schimmer, konnte alle anderen Aufgaben lösen, hier habe ich keinen blassen Schimmer.

Bei der Kombinatorik, so meinte es mal mein Mathedozent im Bachelor, was gute 1 und halb Jahre her ist, ist es erstmal wichtig, haben wir eine Wiederholung oder haben wir keine.

Hier haben wir eine Wiederholung, das bekomme ich noch hin!

Unser n ist 17, da 17 Felder, die man belegen kann, auch das bekomme ich noch hin!
Beim k hörts aber gewaltig auf :( Ich habe 8 schwarze, 8 weiße Steine und 1 freie Stelle oder? Ist dann k auch 17 oder wie sehen wir das?

AUßerdem suchen wir ja die Anzahl der möglichen Zustände, mit Wiederholung, das wäre die Formel oder:

aber wie wende ich die Formel an?:

gerade deise k_1 bis k_s, warum so viele k´s ?

Teilen Diese Frage melden

gefragt 17.09.2023 um 20:19

usercd9159
Punkte: 12

Ja, dann wären
- n = Anzahl der freien Felder = 17
- s = Anzahl der Möglichkeiten, wie ein Feld belegt sein kann = 3.
$\;\;$ Nämlich schwarz, weiß, frei.

Demzufolge gibt es drei k's, nämlich
- $ k_1$ = Anzahl der schwarzen Steine = 8
- $ k_2$= Anzahl der weißen Steine = 8
- $ k_3$ = Anzahl der leeren Felder = 1

Und dann kann man Deine Formel anwenden.

Allerdings kann es natürlich sein, dass einige Zustände nicht durch die erlaubten Züge aus der Anfangsstellung erreicht werden können, weswegen ich mir bei meiner Antwort nicht ganz sicher bin.

Ich finde, hier hätte der Dozent auch einen ganzen Punkt spendieren können! ─ m.simon.539 18.09.2023 um 01:49

Danke wie genau entsteht hier eigentlich die Wiederholung? Also habe das mir aich gedacht, verstehen tue ich es aber nicht, ein Feld kann ja in einem Zustand nur einmal belegt sein und nicht 2x ? ─ usercd9159 18.09.2023 um 02:38

Da ja nun - vorausgesetzt, dass alle Zustände durch die erlaubten Züge aus der Anfangsstellung auch tatsächlich erreicht werden können - die Lösung klar ist $\left(\frac{17!}{8!\cdot8!}\right)$, erlaube ich mir noch einen Hinweis auf einen anderen Ansatz: Die Positionen der schwarzen Steine bilden jeweils eine $8$-elementige Teilmenge der $17$ möglichen Positionen. Dabei haben die weißen Steine jeweils genau $9$ Möglichkeiten der Anordnung (das "Loch" kann an $9$ Stellen sein). Wenn man weiß, dass $\binom{n}{k}$ die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Grundmenge ist, erhält man auch hier
$9\cdot\binom{17}{8} = 9\cdot\frac{17!}{8!\cdot(17-8)!} = \frac{17!}{8!\cdot8!}$. ─ user77e28f 18.09.2023 um 10:37

Es ist tatsächlich so, dall alle möglichen Zustände aus dem Anfangszustand wie in der Spielregel beschrieben erreicht werden können. Hab's soeben mit einem Java-Programm nachgewiesen. ─ m.simon.539 18.09.2023 um 21:07

"Mit Wiederholung" heißt nur: Manche Objekte sind untereinander gleich. So sind die 8 weißen Kugeln untereinander gleich, sowie die 8 schwarzen.
"Ohne Wiederholung" heißt: Alle Objekte sind verschieden. Das ist der einfachere Fall.

─ m.simon.539 18.09.2023 um 21:13

Kommentar schreiben

1 Antwort

Jetzt Antwort schreiben

cauchy · Accepted Answer · 2023-09-18T04:25:21Z

1

Es geht hier um eine Anordnung von 17 Objekten (Permutation) mit Wiederholung, da das Vertauschen der Steine gleicher Farbe zur selben Anordnung führt. Das Vertauschen der gleichen Farbe untereinander ist dann die Wiederholung, da die einzelnen Steine nicht unterscheidbar sind.

Teilen Diese Antwort melden Link

geantwortet 18.09.2023 um 04:25

cauchy
Selbstständig, Punkte: 30.62K

Danke beim Nenner machen wir ja 8!*8!*1!, das kommt ja davon, dass wir 3 verschiedene Möglichkeiten haben und von denen 8x weiße, 8x schwarze und 1x leeres Feld oder? Wenn alle Steine schwarz wären und ein Feld leer, würde man dann 17!/16! machen? Oder wie genau ist das mit den k‘d im Nenner? ─ usercd9159 18.09.2023 um 11:20

Das ist jeweils die Anzahl der Möglichkeiten, die $k_i$ Steine einer Farbe anzuordnen. Da diese Anordnungen aber alle gleich sind, wird diese Anzahl aus der Gesamtzahl der Anordnungen $n! $ rausdividiert. ─ cauchy 18.09.2023 um 12:30

Kommentar schreiben