2

立方体の6面色塗りの総数を数学で解決!

991
0

立方体の6面色塗りの総数をJulia で解決!
https://zenn.dev/dannchu/articles/c2d1b6181c1c1b

を読んで書いた記事です。

立方体の面の塗り分けを行い、回転して重なるものは同一視する、という問題ですが、
これは群論を用いることで手計算でも簡単に答えを得ることができます。

同値類

集合Xに対して、関係 (xyの真偽が定まる) を定める時、以下の条件を満たしていれば同値関係といい、xyを xとyが同値という。

  1. 反射律
    xx
  2. 対称律
    xyyx
  3. 推移律
    xy  yzxz

元xと同値なものの集合をxの同値類という。
[x]={y|xy}
また、Xを同値類に分割できる。この操作を同値類で割るという。
X/ ={[x]|xX}

Xのすべての元は最低でも自分自身を含む同値類に入るので、必ずどれかの同値類に入っている。
異なる同値類に入っているものが重複することはない。もしそうなるとその2つの同値類のどのペアを取ってきても、共通に入っている元による推移律によって最初から同値だったことになってしまうからである。

集合G、
Gの元e(単位元)、
単項演算1 (a逆元) (aG に対し a1のように使うと、x1Gになっている)
二項演算 () (x,yGに対し xyのように使うと、xyGになっている)
の組(G,e,1,)で、以下の条件を満たすものをという

1.単位元は掛けてもなにもしない
ex=xe=x

2.逆元とくっつくと消える(なにもしない単位元になる)
xx1=x1x=e

3.結合法則
(xy)z=x(yz)
これがあるので、xyzと書く場合があるが、どちらにしてもよいということがわかる。

作用

群Gと集合Xに対して、(左)作用という演算を定義する。
gG,xX のとき、 gxX

  1. 単位元は作用でも何もしない
    ex=x
  2. 作用はでまとめて作用できる
    (g1g2)x=g1(g2x)

群の定義と作用の定義より、
(gg1)x=(g1g)x=x

作用は同値関係を定める

xygy=gx とすると、

  1. x=ex
  2. y=gxx=g1y
  3. z=g1yy=g2xz=(g1g2)x
    なので、同値関係になる。このとき、各同値類を軌道という。
コーシー・フロベニウスの定理

Gが集合Xに作用しているとき、その軌道X/Gとする。
また、Gの元gで動かないXの点の集合(固定点集合)を Xg={x|gx=x} と書くとき、
|G||X/G|=gG|Xg|
(|X|Xの濃度(元の数)を表します。)

|G|:|X/G|:|Xg|:gG

左辺と右辺とを1対1で対応させる
まず、同値類ごとに代表として元を1つ選んでおく。[x]の代表元をc[x]

右辺 (g,y)(gG,yXg) が与えられたとする。
x=c[y]とすると、y[y]=[x]で、xyになるので、
あるhy,xが存在してy=hy,xxと書ける。
右辺から左辺に、f:(g,y)(ghy,x,[y]) という写像で対応させる。

逆に 左辺(g,[x])(gG,[x]X/G)が与えられたら、
x0=c[x]として、
f:(g,[x])(ghgx0,x01,gx0)
とすると、
f(f(g,y))=f(ghy,c[y],[y])(x=c[y])=f(ghy,x,[x])=(ghy,xh(ghy,x)x,x1,(ghy,x)x)=(ghy,xhy,x1,y)=(g,y)

f(f(g,[x]))=f(ghgx,x1,gx)(xc[x]使)=(ghgx,x1hgx,x,[gx])=(g,[x])
よって、一対一で対応していることがわかる。

[x]からxを出すときなどにc[x]などを使って、細心の注意を払っているのは、well-defined性といって、
X/などの集合からの関数を作るときは、xyf([x])=f([y])になるようにする必要があり、
そうしないと同じはずの元から違う結果が返ってくるようなことになり、関数にならないという問題があるからです。

重複円順列

赤球、白球がたくさんあるとき、これらのうち6つを円状に並べる方法はいくつあるか。
回転で重なるものは同じとする。

群Gを巡回群C6とする。これは
|C6|={0,1,2,3,4,5}e=0a1={6a(a>0)0(a=0)aba+bmod6
なる群である。

Xを(0,0,0,0,0,0)(1,1,1,1,1,1)26要素の集合とし、
作用を(gx)i=x(i+g)mod6で定義する。
例: g=3,x=(1,0,1,0,0,1)なら、gx=(0,0,1,1,0,1)

そうすると、

  • g=0のとき、xのすべての元は動かないので |Xg|=64
  • g=1,5のとき、すべてのiについてxi=xi+1でないといけないので、
    結局すべてのxiが同じ場合のみ重なる |Xg|=2
  • g=2,4のとき、x0=x2=x4,x1=x3=x5 |Xg|=4
  • g=3のとき、x0=x3,x1=x4,x2=x5 のとき重なるので |Xg|=8

|X/G|=64+2×2+2×4+86=846=14

立方体の彩色1 (元記事にあった問題)

立方体の6面を赤色、青色、黄色の3色で2面づつ塗り分ける方法は何通りか。
回転で重なるものは同じとする。

群Gを立方体を回転(鏡写しはふくまない)して重ねる方法の全体、
eを動かさない操作、
a1をaの逆の回転、
baをaのあとにbを行う操作とする。
サイコロで考えると、1の行き先が6種類、2はその隣の面4つのどれかなので、24通りの回転があるが、後々のために別の方法で分類する。

  1. 回転なし(1種)
  2. 面中心90度回転(6種)
  3. 面中心180度回転(3種)
  4. 頂点を1/3周回す(8種)
  5. 辺の中点を中心に回転し、隣り合う面を入れ替える(6種)
    • 選んだ辺の両側、真反対の両側、側面同士が入れ替わる

Xは立方体を回転を考えずに塗る方法なので、6C24C2要素ある。
|Xg|を考える。上の類別ごとに、

  1. すべて重なる。6C24C290通り。
  2. 回転軸以外の4つの面の色が等しい必要があるので不可能。
  3. 側面の向かい合うペアがそれぞれ等しいので、 軸とそれぞれのペアに割り当てる色を選んで3!=6通り
  4. 回す頂点の周りの3面がそれぞれ等しい必要があるので不可能。
  5. 選んだ辺の両側、真反対の両側、側面同士が等しいので、それぞれのペアに割り当てる色を選んで3!=6通り

|X/G|=90+3×6+6×624=14424=6

立方体の彩色2

立方体の6面を赤色、青色、黄色の3色で塗り分ける方法は何通りか。
使わない色があったり全ての面を同じ色に塗ってもよく、回転で重なるものは同じとする。

Xは立方体を回転を考えずに塗る方法なので、36要素ある。
|Xg|を考える。上の類別ごとに、

  1. すべて重なる。36729通り。
  2. 回転軸以外の4つの面の色が等しい必要があるので、3327通り。
  3. 側面の向かい合うペアがそれぞれ等しいので、 3481通り。
  4. 回す頂点の周りの3面がそれぞれ等しいので、 329通り。
  5. 選んだ辺の両側、真反対の両側、側面同士が等しいので、3327通り

|X/G|=729+6×27+3×81+8×9+6×2724=136824=57

投稿日:2022521
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中