Kleines Problem mit grossen Zahlen

Dass es bei Bitboard sehr viele mögliche Muster gibt, ist nichts neues. Allerdings sind es nicht 1’361’129’467’683’753’853’853’498’429’727’072’845’824 wie ich bis anhin kommuniziert habe. Ein findiger Leser hat auf Neuerdings.com kommentiert

…nochmal die “rein mathematisch” theoretisch moeglichen varianten-anzahl nachzurechnen. die muss sich mindestens halbieren, da alle muster auf dem kopf die gleichen schneidebretter darstellen (und viele sogar noch an der mittellinie gespiegelt werden koennen)…

– mathe-dings

Hm, touché. Jetzt möchte ich natürlich gerne wissen, wie viele Möglichkeiten es nun wirklich gibt. Deshalb mein Aufruf an alle Mathematiker und sonstigen Zahlenzauberern: Was ist die richtige Lösung (und wie errechnet man so was)?

8 Kommentare zu “Kleines Problem mit grossen Zahlen

  1. hoi samuel, also ich wĂĽrde sagen es sind 2 hoch (10 mal 13) geteilt durch 2. bei jedem bit gibt es 2 möglichkeiten: hell oder dunkel, also 2 * 2 * 2 … insgesamt 130 mal. da ein rechteck, wie oben bemerkt, jeweils um 180° gespiegelt werden kann, muss das resultat also noch durch 2 geteilt werden. insgesamt also 2 hoch 129. im excel kann ich die zahl aber nicht richtig darstellen…

    was waren denn die meinungen der anderen „mathematiker“?

    gruess vom sofa,
    leo

    • Hallo Leo, vielen Dank fĂĽr deine Berechnung. Mit dem ersten Teil bin ich einverstanden (2 hoch 129). Doch danach gibt’s nochmals weniger Muster weil das Bitboard nicht nur um 180° gedreht, sondern auch umgekehrt (Unterseite nach oben) werden kann. Die Lösung wird wohl zwischen den von dir errechneten 680 Sextillionen und 340 Sextillionen sein.
      Gruss Samuel

  2. Auch nach längerer Betrachtung keine Chance meinerseits. Das Problem ist komplexer als es auf den ersten Blick scheint… mit fremder Hilfe (Rene Gruber) hier die Lösung:

    Zitat: „Wenn es nur um diese 180Grad-Drehung geht, dann muss man exakt nur diejenigen Färbungen ermitteln, die bei so einer Drehung in sich selbst ĂĽbergehen: Das sind genau 2 hoch 65 , denn man kann eine „Hälfte“ 5×13 beliebig färben, die andere Hälfte ergibt sich dann zwangsläufig durch diese Drehungsbedingungen.

    Macht summa summarum
    (2 hoch 130 + 2 hoch 65)/2 = 2 hoch 129 + 2 hoch 64 Färbungen.“
    Zitat Ende…

    Hier ist aber (vorerst mal) NUR die Drehung um 180° berücksichtigt!
    Mach also 6805 64733 84187 69269 45195 95893 72459 74528
    Möglichkeiten (39 Stellen)

    Grussli!

    • Hallo Urs, vielen Dank fĂĽrs Rechnen. Ich möchte jedoch gern ‚die ganze Wahrheit‘ also inkl. Drehung um die Mittelachse. Bin gespannt wer das ausrechnen kann…
      Beste GrĂĽsse

      • VOILA! Die Ăśberlegungen sind die folgenden, man muss ’nur‘ richtig an die Sache rangehen…

        Da gibt es einmal die Spiegelung 5./6.Reihe: Da kann man ebenfalls wieder die eine Hälfte 5×13 beliebig färben, und der Rest ergibt sich daraus. Macht also wieder 2^{65} bzgl. dieser Spiegelung invariante Färbungen.

        Und dann gibt es da noch die Spiegelung an der Mitte der 7.Spalte: Hier kann man die Spalten 1 bis 7 der 13 Spalten beliebig färben, die Spalten 8 bis 13 ergeben sich im Invarianzfall aus den Färbungen der Spalten 1 bis 6, während die 7.Spalte ja in sich selbst übergeht. Hier gibt es also 2^{70} invariante Färbungen.

        Summa summarum gibt es nach Burnside-Lemma (siehe Wikipedia) dann genau

        {2^{130}+2^{70}+2^{65}+2^{65}}/{4} = 2^{128}+2^{68}+2^{64}
        = 3402 82366 92093 84637 76969 25668 48305 88928 (39 Stellen)

        bzgl. Drehung und Spiegelung invariante Färbungen. Genug Varianten, damit jeder Erdenbürger sein individuelles Brett haben kann.

        Viel Spass damit harhar :-)
        Urs Meierhofer

Kommentar schreiben

Folgende Tags sind erlaubt: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>