Pferdchen hüpf < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ein Springer macht auf einem unendlichen Schachbrett 7 Rösselsprünge.
a) Wie viele verschiedene Wege gibt es vom Startpunkt zu jedem Punkt auf dem Brett?
b) Wie viele Wege gibt es ins besondere wieder zum Ausgangspunkt zurück? |
moin,
Bei dieser Aufgabe stecke ich grad ein wenig fest...
Ich hab erstmal so angefangen:
Seien $a,b [mm] \in \IZ$.
[/mm]
Sei (a,b) ein Feld auf dem Schachbrett, dass vom Ausgangspunkt des Springers um a nach oben und um b nach rechts liegt.
- Da $a,b [mm] \in \IZ$ [/mm] erwische ich damit ja jedes Feld auf dem Brett -
Da der Springer in alle 4 Richtungen gleich springen kann (und auch nie gegen eine Mauer rennt) können wir oBdA sagen:
$0 [mm] \leq [/mm] b [mm] \leq [/mm] a$
- gegebenenfalls wird das Schachbrett halt gedreht bzw. es wird "oben" oder "rechts" umdefiniert - alles kein Problem da der Springer in alle Richtungen gleich springen kann -
Nun kann der Springer in einem Zug höchstens um 2 Felder in eine Richtung springen, für $a > 14$ ist der Punkt also mit 7 Sprüngen nicht erreichbar, die Anzahl der Wege ist somit gleich 0.
Das Problem ist jetzt, dass ich selbst mit diesen Überlegungen (die hoffentlich so weit richtig sind^^) immer noch [mm] $15^2 [/mm] = 225$ Zielfelder zu untersuchen habe; deutlich zu viele um sie einzeln von Hand zu betrachten.
Abgesehen davon steh ich grad irgendwie auf dem Schlauch, also mir will partout keine schöne Formel oder ein System dafür einfallen.
Ein Stück über der Aufgabe stand einiges über Multinominalkoeffizienten, also könnten die durchaus irgendwie hilfreich sein.
Ich hoffe jemand kann mir einen Tipp geben wie sich diese Aufgabe lösen lässt.
MfG
Schadowmaster
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:50 So 21.08.2011 | | Autor: | felixf |
Moin!
> Ein Springer macht auf einem unendlichen Schachbrett 7
> Rösselsprünge.
>
> a) Wie viele verschiedene Wege gibt es vom Startpunkt zu
> jedem Punkt auf dem Brett?
> b) Wie viele Wege gibt es ins besondere wieder zum
> Ausgangspunkt zurück?
> moin,
>
> Bei dieser Aufgabe stecke ich grad ein wenig fest...
> Ich hab erstmal so angefangen:
> Seien [mm]a,b \in \IZ[/mm].
> Sei (a,b) ein Feld auf dem
> Schachbrett, dass vom Ausgangspunkt des Springers um a nach
> oben und um b nach rechts liegt.
>
> - Da [mm]a,b \in \IZ[/mm] erwische ich damit ja jedes Feld auf dem
> Brett -
>
> Da der Springer in alle 4 Richtungen gleich springen kann
> (und auch nie gegen eine Mauer rennt) können wir oBdA
> sagen:
> [mm]0 \leq b \leq a[/mm]
>
> - gegebenenfalls wird das Schachbrett halt gedreht bzw. es
> wird "oben" oder "rechts" umdefiniert - alles kein Problem
> da der Springer in alle Richtungen gleich springen kann -
>
> Nun kann der Springer in einem Zug höchstens um 2 Felder
> in eine Richtung springen, für [mm]a > 14[/mm] ist der Punkt also
> mit 7 Sprüngen nicht erreichbar, die Anzahl der Wege ist
> somit gleich 0.
>
> Das Problem ist jetzt, dass ich selbst mit diesen
> Überlegungen (die hoffentlich so weit richtig sind^^)
> immer noch [mm]15^2 = 225[/mm] Zielfelder zu untersuchen habe;
> deutlich zu viele um sie einzeln von Hand zu betrachten.
> Abgesehen davon steh ich grad irgendwie auf dem Schlauch,
> also mir will partout keine schöne Formel oder ein System
> dafür einfallen.
>
> Ein Stück über der Aufgabe stand einiges über
> Multinominalkoeffizienten, also könnten die durchaus
> irgendwie hilfreich sein.
>
> Ich hoffe jemand kann mir einen Tipp geben wie sich diese
> Aufgabe lösen lässt.
Seien $X, Y, Z, W, A, B, C, D$ die acht verschiedenen Spruenge, die so ein Springer machen kann. Damit kannst du 7 Roesselspruenge schreiben als ein Wort der Laenge 7 mit Buchstaben X, Y, Z, W, A, B, C, D.
Beachte jetzt, dass $X Y = Y X$, $X Z = Z X$, $X W = W X$, $Y Z = Z Y$, ... ist. Jeder Rosssprung kann man also normalisiert schreiben als [mm] $A^a B^b C^c D^d X^e Y^f Z^g W^h$ [/mm] mit $a + b + c + d + e + f + g + h = 7$ und $a, b, c, d, e, f, g, h [mm] \ge [/mm] 0$. Die Anzahl der Roessspruenge, die zu diesem Aequivalent ist, kann durch einen Multinomialkoeffizienten angegeben werden (betrachte dazu $(X + Y + Z + W + A + B + C + [mm] D)^7$ [/mm] und wende den Multionomialsatz an).
Jetzt ist noch die Frage, wieviele der "normalisierten" Spruenge [mm] $A^a B^b C^c D^d X^e Y^f Z^g W^h$ [/mm] zu einem Feld $(x, y)$ fuehren. Dazu zuerst die Zuordnung
* $A [mm] \to [/mm] (1, 2)$
* $B [mm] \to [/mm] (2, 1)$
* $C [mm] \to [/mm] (1, -2)$
* $D [mm] \to [/mm] (2, -1)$
* $X [mm] \to [/mm] (-1, 2)$
* $Y [mm] \to [/mm] (-2, 1)$
* $Z [mm] \to [/mm] (-1, -2)$
* $W [mm] \to [/mm] (-2, -1)$
Dann hat [mm] $A^a B^b C^c D^d X^e Y^f Z^g W^h$ [/mm] den Zielpunkt $(a + 2 b + c + 2 d - (e + 2 f + g + 2 h), 2 a + b - (2c + d) + 2 e + f - (2 g + h))$.
Jetzt musst du rausfinden, welche Wahlen von $a, b, c, d, e, f, g, h [mm] \ge [/mm] 0$ mit $a + b + c + d + e + f + g + h = 7$ den Ausdruck $(x, y)$ ergeben. Die passenden Multinomialkoeffizienten addiert ergibt die Gesamtzahl der Wege.
LG Felix
|
|
|
| |
|
So, dann mach ich mal weiter mit der Aufgabe.^^
Erstmal danke felix.
Ich habe versucht einen geschickten Weg zu finden, das ganze zu berechnen, hab aber nix gefunden.
Also hab ich es so gemacht (mit Maple):
| 1: |
| | 2: | #wir definieren die einzelnen möglichen Sprünge des Springers:
| | 3: | S := [[-1,-2],[-2,-1],[-2,1],[1,-2],[-1,2],[2,-1],[1,2],[2,1]];
| | 4: | #hierbei bezeichnet das Paar [a,b] einen Sprung um a nach rechts und b nach oben
| | 5: |
| | 6: | #nun werden alle erreichbaren Felder durchnummeriert:
| | 7: | M := Matrix(29,29,0);
| | 8: | #hierbei ist M[15,15] der Ursprung
| | 9: |
| | 10: | #jetzt wird (stupide/brute force) durchgezählt, wie viele Wege es zu einem beliebigen Feld gibt...
| | 11: |
| | 12: | hallo := proc(N::Matrix)
| | 13: | local a,b,c,d,e,f,g,h,x,y;
| | 14: | for a from 0 to 7 do
| | 15: | for b from 0 to 7 do
| | 16: | for c from 0 to 7 do
| | 17: | for d from 0 to 7 do
| | 18: | for e from 0 to 7 do
| | 19: | for f from 0 to 7 do
| | 20: | for g from 0 to 7 do
| | 21: | for h from 0 to 7 do
| | 22: | if (a+b+c+d+e+f+g+h = 7) then
| | 23: | x := a*S[1] + b*S[2] + c*S[3] + d*S[4] + e*S[5] + f*S[6] + g*S[7] + h*S[8] + [15,15];
| | 24: | y := 7!/(a!*b!*c!*d!*e!*f!*g!*h!); #Anzahl der Wege, da kommutativ
| | 25: | N[op(x)] := N[op(x)] + y;
| | 26: | end if;
| | 27: | end do;
| | 28: | end do;
| | 29: | end do;
| | 30: | end do;
| | 31: | end do;
| | 32: | end do;
| | 33: | end do;
| | 34: | end do;
| | 35: | return N;
| | 36: | end proc:
| | 37: |
| | 38: |
| | 39: | hallo(M);
|
Somit gibt es also auch keinen Weg in 7 Schritten, der wieder beim Ausgangspunkt endet.
Ist das soweit richtig?
Und noch wichtiger: Gibt es einen (deutlich) schöneren Weg oder ist diese Bruteforce-Lösung schon die hübscheste?
thx für Antworten
MfG
Schadowmaster
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:06 So 25.09.2011 | | Autor: | abakus |
> So, dann mach ich mal weiter mit der Aufgabe.^^
>
> Erstmal danke felix.
>
> Ich habe versucht einen geschickten Weg zu finden, das
> ganze zu berechnen, hab aber nix gefunden.
> Also hab ich es so gemacht (mit Maple):
>
> | 1: |
| | 2: | > #wir definieren die einzelnen möglichen Sprünge des
| | 3: | > Springers:
| | 4: | > S :=
| | 5: | > [[-1,-2],[-2,-1],[-2,1],[1,-2],[-1,2],[2,-1],[1,2],[2,1]];
| | 6: | > #hierbei bezeichnet das Paar [a,b] einen Sprung um a nach
| | 7: | > rechts und b nach oben
| | 8: | >
| | 9: | > #nun werden alle erreichbaren Felder durchnummeriert:
| | 10: | > M := Matrix(29,29,0);
| | 11: | > #hierbei ist M[15,15] der Ursprung
| | 12: | >
| | 13: | > #jetzt wird (stupide/brute force) durchgezählt, wie viele
| | 14: | > Wege es zu einem beliebigen Feld gibt...
| | 15: | >
| | 16: | > hallo := proc(N::Matrix)
| | 17: | > local a,b,c,d,e,f,g,h,x,y;
| | 18: | > for a from 0 to 7 do
| | 19: | > for b from 0 to 7 do
| | 20: | > for c from 0 to 7 do
| | 21: | > for d from 0 to 7 do
| | 22: | > for e from 0 to 7 do
| | 23: | > for f from 0 to 7 do
| | 24: | > for g from 0 to 7 do
| | 25: | > for h from 0 to 7 do
| | 26: | > if (a+b+c+d+e+f+g+h = 7) then
| | 27: | > x := a*S[1] + b*S[2] + c*S[3] + d*S[4] + e*S[5] + f*S[6] +
| | 28: | > g*S[7] + h*S[8] + [15,15];
| | 29: | > y := 7!/(a!*b!*c!*d!*e!*f!*g!*h!); #Anzahl der
| | 30: | > Wege, da kommutativ
| | 31: | > N[op(x)] := N[op(x)] + y;
| | 32: | > end if;
| | 33: | > end do;
| | 34: | > end do;
| | 35: | > end do;
| | 36: | > end do;
| | 37: | > end do;
| | 38: | > end do;
| | 39: | > end do;
| | 40: | > end do;
| | 41: | > return N;
| | 42: | > end proc:
| | 43: | >
| | 44: | >
| | 45: | > hallo(M);
| | 46: | > |
>
> Somit gibt es also auch keinen Weg in 7 Schritten, der
> wieder beim Ausgangspunkt endet.
>
> Ist das soweit richtig?
> Und noch wichtiger: Gibt es einen (deutlich) schöneren
> Weg oder ist diese Bruteforce-Lösung schon die
> hübscheste?
>
>
> thx für Antworten
>
> MfG
>
> Schadowmaster
>
Hallo,
jeder Rösselsprung ist mit einem Farbwechsel verbunden. Man springt von einem schwarzen Feld immer auf ein weißes und umgekehrt. Somit kann das Startfeld nie mit einer ungeraden Anzahl von Sprüngen erreicht werden.
Gruß Abakus
|
|
|
|
