Beispiel 443

  • 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!

  • 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

  • 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

  • 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.

  • 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.

    Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders!
    www.chuckbronson.net
    www.spreadshirt.net/shop.php?sid=104618
    - TU-Funshirt-Shop

    Zitat von peszi_forum

    Schiefe optik? siehe dazu den atttachment.. Und deine reaktion war wirklich robot mäßig bei antworten geben

  • 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

  • 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 ...

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



    hi, i'm a signature virus. copy me into your signature to help me spread.

  • 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.

    Otto: Apes don't read philosophy. - Wanda: Yes they do, Otto, they just don't understand
    Beleidigungen sind Argumente jener, die über keine Argumente verfügen.
    «Signanz braucht keine Worte.» | «Signanz gibts nur im Traum.»


    Das neue MTB-Projekt (PO, Wiki, Mitschriften, Ausarbeitungen, Folien, ...) ist online
    http://mtb-projekt.at

  • 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

  • @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


  • 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<sub>i</sub> 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<sub>i</sub> gilt: |A<sub>i</sub>|=7!;
    man muss berechnen:
    |X|
    -Summe der Kardinalitäten aller A<sub>i</sub>
    +Summe der Kardinalitäten aller Durchschnittsmengen von je 2 A<sub>i</sub>
    -Summe der Kardinalitäten aller Durchschnittsmengen von je 3 A<sub>i</sub>
    +Summe der Kardinalitäten aller Durchschnittsmengen von je 4 A<sub>i</sub>
    -Summe der Kardinalitäten aller Durchschnittsmengen von je 5 A<sub>i</sub>
    +Summe der Kardinalitäten aller Durchschnittsmengen von je 6 A<sub>i</sub>
    -Summe der Kardinalitäten aller Durchschnittsmengen von je 7 A<sub>i</sub>
    +Summe der Kardinalitäten aller Durchschnittsmengen von je 8 A<sub>i</sub>


    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 ;)

  • 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

    Otto: Apes don't read philosophy. - Wanda: Yes they do, Otto, they just don't understand
    Beleidigungen sind Argumente jener, die über keine Argumente verfügen.
    «Signanz braucht keine Worte.» | «Signanz gibts nur im Traum.»


    Das neue MTB-Projekt (PO, Wiki, Mitschriften, Ausarbeitungen, Folien, ...) ist online
    http://mtb-projekt.at

  • 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

  • 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

    hi, i'm a signature virus. copy me into your signature to help me spread.

  • 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...

  • 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.