Königliche Kombinatorik < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 17:08 Di 30.11.2004 | | Autor: | Hanno |
Hallo!
Wie viele Möglichkeiten gibt es, mit einem König auf einem Schachfeld von Position A1 nach Position H8 zu gelangen (also von der Ecke unten links zur Ecke oben rechts), wenn man in jedem Schritt nur nach oben, nach rechts, oder diagonal gehen darf?
Viel Spaß!
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:14 Mi 01.12.2004 | | Autor: | Hanno |
Hallo!
Es würde mich interessieren, in welche Regionen ihr die besagte Anzahl an Möglichkeiten einschätzen würdet? Ich habe die Aufgabe schon einigen gestellt und die Erwartungen waren doch ein wenig verwunderlich.
Also, was meint ihr? 50, 100, 1000, 50000, 250000, eine Million oder gar mehr?
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:21 Mi 01.12.2004 | | Autor: | Teletubyyy |
HI Hanno
Ich denke es wäre wohl langweilig wenn ich jetzt schon die exakte Lösung poste.
Da das mit dem König, Schachbrett und dann mal ausprobieren und mitzählen aber nicht so ganz geklappt, wie ich mir es gewünscht hatte,
muss ich zu meiner Schande aber gestehen, dass ich gleich mal an rund 10 000 000 etwa dachte, hab mich wohl von der Geschichte mit den [mm] 2^{63} [/mm] Reiskörnern irregeführen lassen und dachte hier läuft der Hase so ähnlich.
Gruß Samuel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:34 Mi 01.12.2004 | | Autor: | Hanno |
Hallo Samuel!
Tu dir keinen Zwang an, wenn du die Lösung gefunden hast, dann kannst du sie gerne posten.
Liebe Grüße,
Hanno
|
|
|
| |
|
Hallo Hanno,
also ich vermute mal, bei drei möglichen Zügen und einer durchschnittlichen Schrittanzahl von 12 (die Mitte zwischen minimal 8 und maximal 16) sind es etwa [mm] 3^{12}=531441.
[/mm]
Hugo
|
|
|
| |
|
Also, ich bin auch exakt 33722 Möglichkeiten gekommen!
wie?:
Ich hab mir ein Schachbrett aufgamalt und mir in die unten Reihe und in die linke Spalte ne 1 reingeschreiben. (Es gibt jeweils exakt eine Möglichkeit auf jedes dieser Felder mit den Schrittmöglichkeiten rechts,hoch,diagonal)
Jedes Feld Weitere Feld kann nun von unten, links oder vond unten-links betreten werden. Die Anzahl der Möglichkeiten dieses Feld (von A1 aus) zu betreten ist also:
"die des Feldes darunter" + "die des Feldes links davon" + "die des Feldes unten-links davon"
Nun noch ein bisschen in den TR tippen und schon strahlt die Tabelle entgegen;
|A|B |C |D |E |F |G |H
8 ||1|15|113|578|2244|6865|16861|33722
7 ||1|13|85 |377|1289|3332|6664 |16861
6 ||1|11|61 |231|681 |1362|3332 |6865
5 ||1|9 |41 |129|321 |681 |1289 |2244
4 ||1|7 |25 |63 |129 |231 |377 |578
3 ||1|5 |13 |25 |41 |61 |85 |113
2 ||1|3 |5 |7 |9 |11 |13 |15
1 ||1|1 |1 |1 |1 |1 |1 |1
Ich muss zwar zugeben, dass es wohl keine 'unelegantere' Lösung geben kann(ausser alle durchprobieren mit Strichliste ), aber das wichtigste ist doch nur, dass man auch auf die richtige Zahl kommt, und das möglichst schnell!!!
Gruß Samuel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:27 Do 02.12.2004 | | Autor: | Hanno |
Hallo Samuel!
Dein Lösungsansatz ist klasse, nur leider hast du dich verrechnet. Ich habe das ganze mal mit einem kleinen Python Script durchführen lassen:
arr = []
for i in range(0,8):
arr.append([1,1,1,1,1,1,1,1]);
if (i!=0):
for j in range(1,8):
arr[i][j]=arr[i-1][j]+arr[i-1][j-1]+arr[i][j-1];
print arr[7][7];
Und es kommt damit tatsächlich die richtige Lösung heraus! Die verrate ich aber noch nicht, du kannst ja nochmal schauen wo dein REchenfehler lag  Trotzdem: ![[respekt]](/images/smileys/respekt.gif "[respekt]")
Man kann es aber auch gaaaanz stur mathematisch in eine Formel packen und erhält das gleiche Ergebnis - vielleicht findest du die Formel ja auch noch.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:34 Do 02.12.2004 | | Autor: | Teletubyyy |
HI Hanno
Wenn doch nur rechnen könnte....! Ich hab 'nen Rechenfehler für das feld F6 gefunden. Die Tabelle müsste dann so aussehen:
|A|B |C |D |E |F |G |H
8 ||1|15|113|578|2244|7186|19828|48645
7 ||1|13|85 |377|1289|3653|8989 |19828
6 ||1|11|61 |231|681 |1683|3653 |7186
5 ||1|9 |41 |129|321 |681 |1289 |2244
4 ||1|7 |25 |63 |129 |231 |377 |578
3 ||1|5 |13 |25 |41 |61 |85 |113
2 ||1|3 |5 |7 |9 |11 |13 |15
1 ||1|1 |1 |1 |1 |1 |1 |1
Wenn immernoch Fehler drinnstecken dann kannst du mich ja mit deinem kleinen Programm verbessern.
Um das Problem mathematischer anzugehen, hab ich bisher nur eine Idee:
d sei die Anzahl der Diagonalschritte, o derer nach oben und r derer nach rechts
d sei 0 : Lösungen sind Permutationen von 8r und 8o
[mm] $d=0\Rightarrow A_0=\frac{16!}{(8!)^2}$
[/mm]
d sei 1 : Lösungen sind Permutationen von 7r und 7o und 1d
[mm] $d=1\Rightarrow A_1=\frac{15!}{(7!)^2*1!}$
[/mm]
[mm] $d=2\Rightarrow A_2=\frac{14!}{(6!)^2*2!}$
[/mm]
[mm] $d=3\Rightarrow A_3=\frac{13!}{(5!)^2*3!}$
[/mm]
...
Insgesammt ergibt sich also für die Zugmöglichkeiten des Königs:
$A= [mm] \summe_{i=0}^{8}\frac{(16-i)!}{((8-i)!)^2*i!}$
[/mm]
Allerdings bekomme ich jetzt einen viel größeren Wert als oben. Und da ich mal hoffe, dass das oben nicht mehr total falsch ist, und ich mir bei unterem nicht wirklich sicherbin, glaube ich, dass ích da irgendwo einen gewaltigen Denkfehler habe.
Gruß Samuel
|
|
|
| |
|
Puh.
Da bin ich aber froh, dass ich mich nur um den Faktor 10 verschätzt habe.
Hugo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:23 Do 02.12.2004 | | Autor: | Teletubyyy |
Hi Hanno
Du Hast recht! Man startet ja schon auf A1 und muss dann natürlich nur noch 7Diagonal- bzw. 7Rechts- und 7Hoch-Züge machen.
Das mit dem Rechenfehler hab ich inzwischen aber aufgegeben???! Aber das ist auch nicht besonders wichtig, denn der Weg ist doch das Ziel (und nicht die Lösung), oder?
Gruß Samuel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:26 Do 02.12.2004 | | Autor: | Hanno |
Hallo Samuel!
Sehe ich ganz genau so ;))
Ich habe es mir, als ich die Aufgabe gelöst habe, so klar gemacht:
Wenn ich d Diagonalzüge machen will, mache ich insgesamt 14-d Züge, davon d diagonal, 7-d nach oben, 7-d nach unten. Das führt sofort zu folgender Formel, indem ich erst auswähle, wann ich diagonal ziehe, und wann nach oben.
[mm] $A=\summe_{d=0}^{7}{\vektor{14-d\\ d}\cdot\vektor{14-2d\\ 7-d}}=48639$
[/mm]
Liebe Grüße,
Hanno
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
![[]](/images/popup.gif){kind=small}
On-Line Encyclopedia of Integer Sequences