Leichte Kombinatorik < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:59 Mi 07.11.2012 | | Autor: | sissile |
| Aufgabe | | Wieviele Möglichkeiten gibt es, k sich gegenseitig nicht schlagende Türme auf einem n × n Schachbrett zu placieren? |
Es [mm] \vektor{n \\ k} [/mm] Möglichkeiten k der n Zeilen auszuwählen, auf denen die Türme placiert werden sollen.
Weiters gibt es [mm] \vektor{n \\ k} [/mm] Möglichkeiten die SPalte zu wählen in denen die Türme placiert werden sollen..so würden sich aber die Türme gegenseitig schlagen, also muss man die Anzahl einschränken.
Ich komme da nicht weiter..
LG
|
|
| |
|
Hallo sissile,
diese Aufgabe ist mal eine nette Variation der "üblichen", nämlich n Türme auf einem [mm]n\times{n}[/mm]-Feld aufzustellen.
Laut Schachregeln kann ein Turm in "gerader Richtung" so weit ziehen, bis es auf eine andere Figur trifft. Die kann er dann schlagen oder davor stehenbleiben. In der Aufgabe wird allerdings "Schlagen" vorausgesetzt, sowie das völlige Fehlen jedweder anderen Figuren. Das Brett ist also anfangs leer, und dann werden nach und nach k Türme darauf platziert.
Daraus folgt leicht, dass [mm] k\le{n} [/mm] sein muss, denn jeder Turm muss in seiner "Zeile" und "Spalte" allein stehen. Aber zugleich erlaubt die Aufgabe, dass k<n sein="" kann,="" natürlich="" nur="" für="" n="">0. 
> Wieviele Möglichkeiten gibt es, k sich gegenseitig nicht
> schlagende Türme auf einem n × n Schachbrett zu
> placieren?
>
> Es [mm]\vektor{n \\
k}[/mm] Möglichkeiten k der n Zeilen
> auszuwählen, auf denen die Türme placiert werden sollen.
> Weiters gibt es [mm]\vektor{n \\
k}[/mm] Möglichkeiten die SPalte
> zu wählen in denen die Türme placiert werden sollen..so
> würden sich aber die Türme gegenseitig schlagen, also
> muss man die Anzahl einschränken.
> Ich komme da nicht weiter..
Der erste Turm hat alle Möglichkeiten. Er kann in irgendeiner Zeile und irgendeiner Spalte stehen: $n*n$ Optionen...
Der zweite Turm kann nicht in der gleichen Zeile oder Spalte stehen wie der erste. Er hat daher nur [mm] (n-1)^2 [/mm] Optionen; etc.
Wenn wir nun eine Aufstellung von k Türmen gefunden haben und wir nur die Endaufstellung sehen, wissen wir nicht, wie sie zustandegekommen ist. Welcher Turm war wohl der erste, welcher der zweite, etc.?
Für diese Reihenfolge gibt es k! Möglichkeiten.
Insgesamt ist also Folgendes aufzusummieren:
(bei k=0) $1$ Möglichkeit
(bei k=1) [mm] n^2 [/mm] Möglichkeiten
(bei k=2) [mm] n^2*(n-1)^2/2! [/mm] Möglichkeiten
(bei k=3) [mm] n^2*(n-1)^2*(n-2)^2/3! [/mm] Möglichkeiten
usw. bis k=n.
Schau Dir das mal für n=1,2,3,4 an.
Findest Du eine Summenformel?
Übrigens ist tatsächlich diskutabel, ob k=0 erlaubt ist. Das hat natürlich Einfluss auf die gesuchte Formel...
Grüße
reverend
</n>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:35 Do 08.11.2012 | | Autor: | sissile |
Danke für den Post
> Aber zugleich erlaubt die Aufgabe, dass k<n sein="" kann,="" natürlich="" nur="" für="" n="">0.
Was? Ich versteh nur Bahnhoft ..
Was bedeutet dass k=0 ist?0 sich nicht schlagende Türme?
> bei k=3) $ [mm] n^2\cdot{}(n-1)^2\cdot{}(n-2)^2/3! [/mm] $ Möglichkeiten
Das verstehe ich auch nicht.
Ich habe nun was anderes überlegt
Es gibt [mm] \vektor{n\\ k} [/mm] Möglichkeiten k von den n -Zeilen auszuwählen, wo Türme placiert werden und [mm] \vektor{n \\ k} [/mm] Möglichkeiten die k Spalten auszuwählen.
Wie du geschrieben hast:
> Wenn wir nun eine Aufstellung von k Türmen gefunden haben und wir nur die Endaufstellung sehen, wissen wir nicht, wie sie zustandegekommen ist. Welcher Turm war wohl der erste, welcher der zweite, etc.?
In der ersten Zeile hat man k Möglichkeiten von den k Spalten, die zu wählen wo der Turm placiert werden soll.
In der zweiten zeile hat man nur noch k-1 Möglichkeiten...
-> Insgesamt komme ich auf [mm] \vektor{n \\ k} \vektor{n \\ k} [/mm] k!
Was sagst du zu der Lösung?
|
|
|
| |
|
Hallo sissile,
> > Aber zugleich erlaubt die Aufgabe, dass k<n sein="" <br="">> kann,="" natürlich="" nur="" für="" n="">0.
> Was? Ich versteh nur Bahnhoft ..
Aber ich habe doch nur "Bahnhof" gesagt, ganz ohne "t".
Hier scheint übrigens irgendwas mit der Zitierfunktion schief zu laufen. Halten wir zwischendurch mal [mm] 0\le k\le{n} [/mm] fest.
> Was bedeutet dass k=0 ist?0 sich nicht schlagende Türme?
Genau. Und es gibt nur eine Möglichkeit, keinen einzigen Turm auf dem leeren Brett zu platzieren.
> > bei k=3) [mm]n^2\cdot{}(n-1)^2\cdot{}(n-2)^2/3![/mm] Möglichkeiten
> Das verstehe ich auch nicht.
Dann solltest Du nochmal nachdenken.
> Ich habe nun was anderes überlegt
> Es gibt [mm]\vektor{n\\
k}[/mm] Möglichkeiten k von den n -Zeilen
> auszuwählen, wo Türme placiert werden und [mm]\vektor{n \\
k}[/mm]
> Möglichkeiten die k Spalten auszuwählen.
Ja, das ist richtig.
> Wie du geschrieben hast:
> > Wenn wir nun eine Aufstellung von k Türmen gefunden
> haben und wir nur die Endaufstellung sehen, wissen wir
> nicht, wie sie zustandegekommen ist. Welcher Turm war wohl
> der erste, welcher der zweite, etc.?
> In der ersten Zeile hat man k Möglichkeiten von den k
> Spalten, die zu wählen wo der Turm placiert werden soll.
> In der zweiten zeile hat man nur noch k-1
> Möglichkeiten...
> -> Insgesamt komme ich auf [mm]\vektor{n \\
k} \vektor{n \\
k}[/mm]k!
> Was sagst du zu der Lösung?
Deine Lösung ist völlig ok, aber gar nicht anders als meine. Du bist nur kombinatorisch auf anderem Weg dahin gekommen.
Was vielleicht noch bleibt, ist dies: zeige, dass beide Lösungen äquivalent sind.
Grüße
reverend
</n>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:04 Do 08.11.2012 | | Autor: | sissile |
okay danke dafür ;)
LG
|
|
|
|
