Beispiel 443
Results 1 to 19 of 19

Thread: Beispiel 443

  1. #1
    dj_m.o.h.t.'s Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    428
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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!

  2. #2

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien 23
    Posts
    50
    Thanks
    0
    Thanked 0 Times in 0 Posts

    mal ein Ansatz

    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

  3. #3
    lj_scampo's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Posts
    582
    Thanks
    0
    Thanked 0 Times in 0 Posts

    @Geli - Ansatz

    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

  4. #4

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  5. #5
    MarvinTheRobot's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Location
    48° 09′ N, 16° 27' E
    Posts
    1,753
    Thanks
    121
    Thanked 105 Times in 58 Posts
    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
    Quote Originally Posted by peszi_forum
    Schiefe optik? siehe dazu den atttachment.. Und deine reaktion war wirklich robot mäßig bei antworten geben

  6. #6
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    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

  7. #7

    Title
    Master
    Join Date
    Dec 2001
    Location
    Wien, 8.
    Posts
    100
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also wenn mein kleines simulations programm zu diesem bsp. nicht fehler haft ist, ist 14833 das ergebnis *nowarranty*
    Last edited by heder; 26-04-2002 at 16:25.

  8. #8

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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 ...

  9. #9

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    kann heders ergebnis bestätigen... bei mir kommt dasselbe raus: 14833


    Code:
     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);
    
        }
    hi, i'm a signature virus. copy me into your signature to help me spread.

  10. #10
    Wings-of-Glory's Avatar
    Title
    CO-Administrator
    Join Date
    Jan 2002
    Posts
    3,989
    Thanks
    338
    Thanked 498 Times in 262 Posts
    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 L={}


    //EDIT: DIE AUFGABE IST LÖSBAR. Hab mich beim zählen der diagonalen Felder vertan.
    Last edited by Wings-of-Glory; 28-04-2002 at 20:58.
    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

  11. #11
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    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 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

  12. #12
    VTEC's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    674
    Thanks
    0
    Thanked 1 Time in 1 Post
    @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
    HaRdCoRe HaS JuSt BeGuN!

  13. #13

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    533
    Thanks
    3
    Thanked 121 Times in 76 Posts
    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<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

  14. #14
    MarvinTheRobot's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Location
    48° 09′ N, 16° 27' E
    Posts
    1,753
    Thanks
    121
    Thanked 105 Times in 58 Posts
    Danke Dimitrij!

    jetz hab ichs verstanden!

    thx, 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
    Quote Originally Posted by peszi_forum
    Schiefe optik? siehe dazu den atttachment.. Und deine reaktion war wirklich robot mäßig bei antworten geben

  15. #15
    Wings-of-Glory's Avatar
    Title
    CO-Administrator
    Join Date
    Jan 2002
    Posts
    3,989
    Thanks
    338
    Thanked 498 Times in 262 Posts
    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
    Attached Images Attached Images  
    Last edited by Wings-of-Glory; 28-04-2002 at 21:06.
    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

  16. #16
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  17. #17

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  18. #18
    nexxyz's Avatar
    Title
    Elite
    Join Date
    Apr 2002
    Location
    Wien
    Posts
    404
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...
    “It is a fool's prerogative to utter truths that no one else will speak.”
    (\)exxyz-Music-Home

  19. #19

    Title
    Master
    Join Date
    Dec 2001
    Location
    Wien, 8.
    Posts
    100
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •