算数について教えて下さい。


オセロは、8x8マスあり、黒か白(2種色)ですが、
全てのマスを白か黒で埋めた場合、
全部で何通りできるのかはどういう式になるのでしょうか。

8x8x2x.....????

(ゲームは関係ありません)

よろしくお願いします。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2012/10/05 01:38:20
  • 終了:2012/10/05 02:13:42

ベストアンサー

id:matryosika No.1

matryosika回答回数36ベストアンサー獲得回数142012/10/05 02:06:55

2^(8×8)=2^64通りです。

64マスのぞれぞれが白か黒の二種類のうちのどれかになることを考えればこのようになります。難しい説明はいくらでもあるのですが、面倒で伝わりにくいので、簡単な例を出します。

白=w,黒=b
・2マスをオセロで埋める場合の数
(b,b),(b,w),
(w,w),(w,b)の四通り。
・3マスをオセロで埋める場合の数
(b,b,b),(b,b,w),(b,w,b),(b,w,w),
(w,w,w),(w,w,b),(w,b,w),(w,w,w)の八通り。

この問題を分岐図で解くと何マスの時でも2^(マス数)となることがわかります。
「1マス目は白か黒か?」で一段階目の分岐、それぞれの分岐について「2マス目は白か黒か?」で二段階目の分岐…と繰り返していくと、樹形図の分岐の数は倍々になっていきます。

id:worldtravel

なるほど!
わかりやすいご説明、ありがとうございます。

勉強になりました。

2012/10/05 02:13:36
id:worldtravel

すみません。

googleでこのように出るのですが
2^64 = 1.84467441 × 10^19

1.84467441 × 100000000000000000000 = 184467441000000000000

1垓8446京7441兆と言うことで宜しいのでしょうか? --;

2012/10/05 02:21:45
  • id:martyan
    ちなみにパターンだけを考えるなら左右対称上下対称でそれ÷4したらいいよ。
  • id:martyan
    万が一実際のゲームの大体の場合の数なんかを知りたいならhttp://www9.atwiki.jp/othello/pages/28.htmlなんかが参考になる。
  • id:Silvanus
    正確には18446744073709551616ですね。
    つまり、1垓8446京7440兆7370億9551万1616です。
  • id:TransFreeBSD
    >1垓8446京7441兆と言うことで宜しいのでしょうか?
    一桁多いです。10^19は0が19個、つまり最上位と合わせて20桁なので5×4の1844京~兆~億~万~となります。
    正確なところはこちらで http://www.wolframalpha.com/input/?i=2%5E64

    >左右対称上下対称でそれ÷4したらいいよ。
    回転対称も忘れず。
    そしてさらに盤自体が対称配置で回転や反転しても元と変わらない(1/4に入らない)パターンも。
    2×2なら2^(2×2)/4=4ではなくて下記6通りになる。
    ○○ ●○ ●● ●○ ●● ●●
    ○○ ○○ ○○ ○● ●○ ●●
    それらを勘案してどういう計算式になるかはわからない。
  • id:tazikisai-mukou
    質問通り『全てのマスを白か黒で埋めた場合』
    全てを「白」で埋め尽くすのは1通り
    全てを「黒」で埋め尽くすのは1通り
    合わせて2通りではないかと思いますが?
  • id:Silvanus
    【訂正】
    >正確には18446744073709551616ですね。
    の行は合ってましたけど、
    >つまり、1垓8446京7440兆7370億9551万1616です。
    では下から5桁目の1が重複してますね!(汗)
    正しくは「1844京6744兆0737億0955万1616」ですね…。
    済みませんです…。
  • id:matryosika
    対称性を考慮したときの解き方も考えたので書きます。(自信はありません 間違っているところあれば指摘をお願いします)

    図をみながらでお願いします→http://f.hatena.ne.jp/matryosika/
    一つ目の図です。8×8のマス目の一部が黄色に塗られています。
    大きな正方形は盤面を反映していて、対角線同士を結んで盤面を4つの領域に分割します。
    実際の盤面は連続的ではなく離散的なので8×8の盤面の中の黄色の領域を分割領域一つ分とします。
    この領域を白黒に分ける場合の数は2^16になります。

    次に、カラフルな3つの図についてです。
    盤面全体が4つの領域に分かれているのを表現しています。
    色の違いはそれぞれの領域の配列が違うことを反映していて、対称性を考慮しなければならない場合の種類を(たぶん)すべて書き出してみました。赤色は定配置で、この話においては変化させません。それ以外の色は変配置(配置の変数版)です。画像ごとに定配置が一つ、二つ、三つと増えていくように書きました。

    次に、式の説明です。総数というのは、定配置を一つ考えた時の並び方の場合の数のことです。式中のnは領域一つ分の配置の場合の数で、今回の場合は2^16です。
    また、回転対称性の数というのは、この正方形を回転させたときに同一視しなければならないものの数です。ここで注意したいのが、赤以外の色は定配置ではないので、それらの配置が入れ替わっても同一視されなければならないという点です。

    この正方形の一つ一つについて総数、回転対称性を考えることによって、次の式で重複される(同一視される)場合の数を求めることができます。
    Σ(総数×(回転対称性-1))
    Σ記号は「すべての場合について次の式を足し合わせよ」という意味で、この場合は、正方形A~Jのすべてについて総数×(回転対称性-1)を実行して、それぞれ足し合わせます。
    結果は、3n^4-8n^3+13n^2-8nとなります。(n=2^16です)
    この値を2^64から引けばいいと思います。

    自信はありませんが、読んでもらえたらうれしいです。意見などご指摘お願いします。
    ただ、リアクションかなり遅れるかもしれませんがご了承ください。
  • id:worldtravel
    全然コメントを見ていませんでした。
    皆さんありがとうございます。

    1桁違いましたね ^^;

    http://www.wolframalpha.com/input/?i=2%5E64
    このようなサイトもあるのですね。

    2通りも正解なのでしょうね ^^;

    対称性の問題もあったのですね。
    そこまで考えていませんでした。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません