Beispiel 443

[dj_m.o.h.t.]

Angabe: Auf wie viele Arten können 8 Türme auf ein Schachbrett gestellt derart gestellt werden, dass sie einander nicht schlagen und die weiße Diagonale frei bleibt? (Ein Turm schlägt eine andere Figur, die horizontal oder vertikal auf gleicher Höhe steht, sofern keine andere Figur dazwischen steht.)

Lösung: I have no idea!

[Geli]

Also, ich denk mal, es gibt drei Möglichkeiten, nämlich einmal, dass sie alle in der schwarzen Diagonale stehen, oder dass sie alle parallel zu weißen diagonela stehen, wobei dann einer im gegenüberliegenden eck stehen muss. Das geht dann noch spiegelverkehrt, also drei Möglichkeiten. Ich nehme mal an, dass sie eh nicht unterscheidbar sind, sonst müsste man sie halt noch permutieren.

Kann das soweit stimmen?

lg, Geli

[lj_scampo]

Meiner Ansicht nach stimmt dieser Ansatz leider nicht :-(
Als Gegenbeispiel hab ich da mal ein kleines Schachbrett improvisiert: die roten Felder sind die verbotenen, die grünen jene, auf denen ein Turm steht.
Wie die Lösung ausschaut, weiß ich leider auch nicht

[qmp]

Damit sich die Türme nicht schlagen können, darf in keiner Zeile und keiner Spalte mehr als 1 Turm stehen.

da es 8 Trüme sind, steht also in jeder Spalte einer und in jeder Zeile einer. Man kann das ganze jetzt als 8-Tupel der Zahlen 1-8 auffassen. Die Postition der Zahl in dem Tupel entspricht der Zeilennummer und die Zahl selber der Spaltennummer.

z.B. 2,6,4,3,1,7,8,5

xTxoxoxo
oxoxoTox
xoxTxoxo
oxTxoxox
Toxoxoxo
oxoxoxTx
xoxoxoxT
oxoxTxox

macht insgesamt 8! = 40320 Permutationen

Das Problem ist jetzt diejenigen Permutationen in denen mindestens eine Figur auf der weißen Diagonale steht herauszufiltern (also Spaltennummer = Zeilennumemr). Das geht mit den Inklusions-Esklusions Prinzip, aber das ist mir bissl zuviel Arbeit.

[MarvinTheRobot]

Lösung: es sind 14833.

Also nach dem inklusions / exklusionsprinzip (kann leider auch nur den letzten schritt aufschreiben):

8!-[7!*(8!/1!*7!)-6!*(8!/2!*6!)+5!*(8!/3!*5!)usw usw bis 1!]

im endeffekt:

8!-(8!/1!)+(8!/2!)-(8!/3!)+(8!/4!)-(8!/5!)+(8!/6!)-(8!/7!)+(8!/8!) = 14833


das ergebnis stimmt. nur fragt mich bitte nicht nach dem ansatz, den hab ich selber nicht ganz kapiert.... vielleicht scan ich meine mitschrift ein, hoffentlich hilfts euch.

;-)


mfg, Phil.

[Zentor]

ich glaube es sind 7! Möglichkeiten.
In der ersten Zeile 7 Felder (alle ausser des weißen Diagonalfeldes)
in der 2.Zeile 6 Felder (alle ausser der des weißen Diag. und des darunterliegenden Feldes aus der 1.Zeile
...
usw.
also 7*6*5*4*3*2*1 =5040.
Aber andererseits sollte das Themengebiet Inklusion/Exklusionsprinzip sein, hm.. wo liegt da mein Denkfehler?
mfg Zentor

[heder]

also wenn mein kleines simulations programm zu diesem bsp. nicht fehler haft ist, ist 14833 das ergebnis *nowarranty*

[qmp]

@Zentor: hab ich mir zuerst auch gedacht, stimmt aber nicht.
1. Zeile 7 Möglichkeiten
2. Zeile 6 Mgl. oder 7 wenn der Turm in der ersten Zeile auf dem Diagonalfeld der zweiten Zeile steht.
...
das pfanzt sich nach unten beliebig fort ...

xTxoxoxo 7 Mgl.
oxoxoxox 7 Mgl.
xoxoxoxo ...

[Chris]

kann heders ergebnis bestätigen... bei mir kommt dasselbe raus: 14833



public static void main(String[] args) {
int cnt=0;
for (int a=0; a<8; a++) { if (a==0) continue;
for (int b=0; b<8; b++) { if ((a==b)||(b==1)) continue;
for (int c=0; c<8; c++) { if ((b==c)||(c==a)||(c==2)) continue;
for (int d=0; d<8; d++) { if ((c==d)||(d==a)||(d==b)||(d==3)) continue;
for (int e=0; e<8; e++) { if ((d==e)||(e==a)||(e==b)||(e==c)||(e==4)) continue;
for (int f=0; f<8; f++) { if ((e==f)||(f==a)||(f==b)||(f==c)||(f==d)||(f==5)) continue;
for (int g=0; g<8; g++) { if ((f==g)||(g==a)||(g==b)||(g==c)||(g==d)||(g==e)||( g==6)) continue;
for (int h=0; h<8; h++) { if ((g==h)||(h==a)||(h==b)||(h==c)||(h==d)||(h==e)||( h==f)||(h==7)) continue;
cnt++;
}}}}}}}}
System.out.println(cnt);

}

[Wings-of-Glory]

Ich habe es mir so vorgestellt:

Ein Schachbrett ist 8x8 Felder groß und hat eine Weiße Diagonale (8 Felder lang)

Für den ersten Turm: 8x8 Felder bzw Möglichkeiten MINUS 8 FELDER (die weiße Diagonale, die man nicht benutzen darf)

Für den zweiten Turm: 7x7 Felder bzw Möglichkeiten MINUS 8-1(=7) FELDER (die weiße Diagonale, die man nicht benutzen darf)

Für den dritten Turm: 6x6 Felder bzw Möglichkeiten MINUS 8-2(=6)FELDER (die weiße Diagonale, die man nicht benutzen darf)

Für den vierten Turm: 5x5 Felder bzw Möglichkeiten MINUS 8-3(=5) FELDER (die weiße Diagonale, die man nicht benutzen darf)

Für den fünften Turm: 4x4 Felder bzw Möglichkeiten MINUS 8-4(=4) FELDER (die weiße Diagonale, die man nicht benutzen darf)

Für den sechsten Turm: 3x3 Felder bzw Möglichkeiten MINUS 8-5(=3) FELDER (die weiße Diagonale, die man nicht benutzen darf)

Für den siebten Turm: 2x2 Felder bzw Möglichkeiten MINUS 8-6(=2) FELDER (die weiße Diagonale, die man nicht benutzen darf)

Für den achten Turm: 1 Feld bzw Möglichkeit MINUS 8-7(=1) FELDER (die weiße Diagonale, die man nicht benutzen darf)
HALT!!: DAS BEDEUTE JA, WIR HABEN NUR MEHR 1 FELD ÜBRIG FÜR TURM 8 DÜRFEN DIESES ABER NICHT BENUTZEN!!

ERGO: DIE AUFGABE IST NICHT LÖSBAR :D L={}

//EDIT: DIE AUFGABE IST LÖSBAR. Hab mich beim zählen der diagonalen Felder vertan.

[Zentor]

Die Aufgabe ist aber lösbar ;)
Du vergisst, das bei deinem Verfahren Felder doppelt weggestrichen werden.
stell z.B. alle Türme auf die schwarze Diagonale. Es gibt sehr viele Möglcihkeiten aber auf die genaue Zahl komm ich noch nicht. Also 7! is zuwenig und 8! zuviel :D Wie man auf 14833 kommt ist mir nicht wirklich klar. Könnt das mal wer in eine Formel packen bzw. erklären wie man auf die Formel von Marvin kommt?

mfg Zentor

[VTEC]

@wings: die aufgabe ist ja lösbar (nur bekomm ich auch was anderes raus)

Ich möcht hier mal meine Ansätze zusammenfassen:

1. ich gehe von der 1. Zeile bis zur 8. Zeile
2. pro Zeile und pro Spalte darf nur 1 Turm sein (d.h. 1 Turm verbraucht 1 Zeile und 1 Spalte)

Verfahren:

Ich möchte mir ansehen, wieviele Stellungen es für 8 Türme gibt, sodaß sie sich nicht schlagen können und ziehe davon die Stellungen ab, in der ein oder mehrere Türme auf der weißen Diagonale stehen

1. Beginn mit der 1. Zeile, der Turm kann hier zwischen 8 verschiedenen Spalten wählen
2. in der 2. Zeile hat der Turm nurmehr 7 verschiedene Spalten zur Verfügung
3. u.s.w.

heraus kommt 8*7*6*5*4*3*2*1=8!

nun zu den Stellungen, auf denen ein oder mehrere Türme auf der weißen Diagonale stehen:

1. in der 1. Zeile gibts nur 1 Möglichkeit, auf der Diagonale zu stehen
2. in der 2. Zeile gibts 7 Möglichkeiten für den Turm, auf einem Feld oder auf der weißen Diagonale, aber nicht auf der vom 1. Turm belegten Spalte zu stehen
3. 6 Möglichkeiten u.s.w.

Es kommt hier 1*7*6*5*4*3*2*1 heraus = 7!

Schlußendlich ergibt sich 8!-7!=7*7!=35280

Anscheinend ist das Ergebnis nicht korrekt, aber vielleicht kann jemand etwas mit dem Ansatz anfangen und daraus eine einfache Rechnung entwickeln.

Marcus

[Dimitrij]

Original geschrieben von MarvinTheRobot
Lösung: es sind 14833.

Also nach dem inklusions / exklusionsprinzip (kann leider auch nur den letzten schritt aufschreiben):

8!-[7!*(8!/1!*7!)-6!*(8!/2!*6!)+5!*(8!/3!*5!)usw usw bis 1!]

im endeffekt:

8!-(8!/1!)+(8!/2!)-(8!/3!)+(8!/4!)-(8!/5!)+(8!/6!)-(8!/7!)+(8!/8!) = 14833


das ergebnis stimmt. nur fragt mich bitte nicht nach dem ansatz, den hab ich selber nicht ganz kapiert.... vielleicht scan ich meine mitschrift ein, hoffentlich hilfts euch.

;-)


mfg, Phil.

Ich kommm auch auf dieses Ergebnis, und ich bin sogar selber draufgekommen ;)

ist eigentlich eh nicht so schwer.
ich versuch's mal zu erklären: (aber meine Erklärungen versteht eh nie jemand)

X sei die Menge der Aufstellungen, wo sich die Türme nicht schlagen;
|X| ist klarerweise 8!.
A_i sei die Menge der Aufstellungen, wo sich die Türme nicht schlagen und wo der Turm in Reihe i auf der weißen Diagonale steht;
Für alle 8 A_i gilt: |A_i|=7!;
man muss berechnen:
|X|
-Summe der Kardinalitäten aller A_i
+Summe der Kardinalitäten aller Durchschnittsmengen von je 2 A_i
-Summe der Kardinalitäten aller Durchschnittsmengen von je 3 A_i
+Summe der Kardinalitäten aller Durchschnittsmengen von je 4 A_i
-Summe der Kardinalitäten aller Durchschnittsmengen von je 5 A_i
+Summe der Kardinalitäten aller Durchschnittsmengen von je 6 A_i
-Summe der Kardinalitäten aller Durchschnittsmengen von je 7 A_i
+Summe der Kardinalitäten aller Durchschnittsmengen von je 8 A_i

die erste Summe besteht aus 8 Summanden, jeder Summand ist 7!
die zweite Summe besteht aus (8 über 2) Summanden, jeder Summand ist 6!
die dritte Summe besteht aus (8 über 3) Summanden, jeder Summand ist 5!
die vierte Summe besteht aus (8 über 4) Summanden, jeder Summand ist 4!
die fünfte Summe besteht aus (8 über 5) Summanden, jeder Summand ist 3!
die sechste Summe besteht aus (8 über 6) Summanden, jeder Summand ist 2!
die siebte Summe besteht aus (8 über 7) Summanden, jeder Summand ist 1
die achte Summe besteht aus (8 über 8) Summanden, jeder Summand ist 0!

Alles klar?
Wahrscheinlich nicht ;)

[MarvinTheRobot]

Danke Dimitrij!

jetz hab ichs verstanden!

thx, phil.

[Wings-of-Glory]

Ich bin auf meinen Fehler draufgekommen.
Ich habe mich beim Abziehen der Diagonalen Felder verzählt
ab dem 5. Turm gibt es keine Weisze-Diagonale mehr, die ich berücksichtigen muss.
Somit kommt bei mir folgendes raus

Turm1=8*8 Felder - 8 Weisse
Turm2=7*7 Felder - 6 Weisse
Turm3=6*6 Felder - 4 Weisse
Turm4=5*5 Felder - 2 Weisse
Turm5=4*4Felder
Turm6=3*3 Felder
Turm7=2*2 Felder
Turm8=1 Feld

8*8 + 7*7 + 6*6 + 5*5 + 4*4 + 3*3 + 2*2 + 1 = 204

204 - 8 - 6 - 4 - 2 = 184

[Shade]

Wo liegt mein Denkfehler?
Ich hab mir das so überlegt:
Mög. für erste zeile=7
Mög. für 2. zeile=6*7(die sieben von der ersten zeile)
Mög. für 3. Zeile=5*6*7
.
.
.
bis 1*2*3*4*5*6*7
letze zeile 1 Möglichkeit
die Möglichkeiten der einzelnen Zeilen werden addiert => 14000 Möglichkeiten

[Chris]

hint:
wenn dein erster turm in der ersten zeile und zweiten spalte steht, hast du für den 2 turm wieder 7 möglichkeiten...

(wenn die weiße diagonale über die felder (1,1),(2,2),...(8,8) geht...

mfg, Chris

[nexxyz]

ein wichtiger denkfehler in vielen der hier angeführten denkansätze ist, dass vergessen wurde, dass die weisse diagonale auch stellen verbieten kann, die sowieso verboten wären, da sich türme schlagen würden -> inklusions/exklusionsprinzip.

z.B.:
in der ersten zeile gibt es 7 möglichkeiten. in der 2. gibt es auch 7 aber wenn der erste turm auf 2,1 steht wird beim ausrechnen das verbotene 2,2er-Feld doppelt abgezogen und so weiter. wäre der erste turm aber auf 5,1 gäbe es nur sechs möglichkeiten für den 2.turm, da er weder in der 2. noch in der 5. stehen dürfte.

hoffe mal, das hat etwas geholfen, zu verstehen, wo das inkl/exklprinz. ansetzt...

[heder]

im prinzip hat, daß der kaiser in der vorlesung mal vorgerechnet, man kann das ganze auch als die anzahl der fixpunkt freien permutationen von 1..8 sehn, fixpunktfrei heißt \pi(i) != i \forall i.