matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMathematik-WettbewerbeKönigliche Kombinatorik
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Mathematik-Wettbewerbe" - Königliche Kombinatorik
Königliche Kombinatorik < Wettbewerbe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Königliche Kombinatorik: Übungsaufgabe
Status: (Übungsaufgabe) Übungsaufgabe Status 
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

        
Bezug
Königliche Kombinatorik: An alle! Schätzt mal!
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Königliche Kombinatorik: 10.000.000!!!
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Königliche Kombinatorik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Königliche Kombinatorik: Schätzwert
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:34 Mi 01.12.2004
Autor: Hugo_Sanchez-Vicario

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

Bezug
        
Bezug
Königliche Kombinatorik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:26 Mi 01.12.2004
Autor: Teletubyyy

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






Bezug
                
Bezug
Königliche Kombinatorik: Antwort
Status: (Antwort) fertig Status 
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]

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

Bezug
                        
Bezug
Königliche Kombinatorik: Verbesserung & Frage
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
Königliche Kombinatorik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:06 Do 02.12.2004
Autor: Hanno

Hallo Samuel!

Du hast immernoch einen Fehler in deiner obigen Tabelle, bist dem richtigen Wert aber schon sehr nahe!

Der Denkansatz in deiner mathematischen Lösung ist auch richtig, aber du hast einen Fehler gemacht, den auch ich zu Beginn gemacht habe: es sind nicht 16, sondern nur 14 Züge, wenn man keinen Diagonalzug macht - und es sind auch nicht 8, sondern maximal 7 Diagonalzüge! Änderst du das, dann erhältst du die Formel

$ A= [mm] \summe_{i=0}^{7}\frac{(14-i)!}{((7-i)!)^2\cdot{}i!} [/mm] = 48639$,

welche dir genau das richtige Ergebnis liefert!

Super! [ok] [ok]

Liebe Grüße,
Hanno



Bezug
                                        
Bezug
Königliche Kombinatorik: knapp daneben
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:39 Do 02.12.2004
Autor: Hugo_Sanchez-Vicario

Puh.

Da bin ich aber froh, dass ich mich nur um den Faktor 10 verschätzt habe.

;-)

Hugo

Bezug
                                        
Bezug
Königliche Kombinatorik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                
Bezug
Königliche Kombinatorik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                        
Bezug
Königliche Kombinatorik: Link zu ganzzahligen Folgen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:05 Fr 03.12.2004
Autor: Peter_Pein

Liebe Leute,

wer - so wie ich - manchmal seine Schwierigkeiten mit diesen kombinatorischen Hirnverzwirnern hat, aber die ersten Folgenglieder durch hinschauen & abzählen ermittelt hat, für den ist die []On-Line Encyclopedia of Integer Sequences ein wahrer Quell der Inspiration :-)

In diesem Fall wäre zum Beispiel die Folge []A001850 diejenige welche.

Viel Spaß damit
Peter

P.S. Wenn jemand die Bezeichnung der Folge der Lottozahlen der (jeweils) nächsten Ziehung gefunden haben sollte, möge sie / er sie mir doch bitte mitteilen!


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]