立方体の６面色塗りの総数を数学で解決！
立方体の６面色塗りの総数をJulia で解決！
https://zenn.dev/dannchu/articles/c2d1b6181c1c1b
を読んで書いた記事です。
立方体の面の塗り分けを行い、回転して重なるものは同一視する、という問題ですが、
これは群論を用いることで手計算でも簡単に答えを得ることができます。
集合Xに対して、関係 $\sim$ ($x \sim y$の真偽が定まる) を定める時、以下の条件を満たしていれば同値関係といい、$x \sim y$を xとyが同値という。
- 反射律
$x \sim x$ - 対称律
$x \sim y \iff y \sim x$ - 推移律
$x \sim y \ かつ \ y \sim z \implies x \sim z $
元xと同値なものの集合をxの同値類という。
$ [x] = \{y | x \sim y \} $
また、Xを同値類に分割できる。この操作を同値類で割るという。
$ X / \sim \ = \{[x] | x \in X\} $
$X$のすべての元は最低でも自分自身を含む同値類に入るので、必ずどれかの同値類に入っている。
異なる同値類に入っているものが重複することはない。もしそうなるとその2つの同値類のどのペアを取ってきても、共通に入っている元による推移律によって最初から同値だったことになってしまうからである。
集合G、
Gの元e(単位元)、
単項演算$◌^{-1}$ ($a$の逆元) ($ a \in G $ に対し $ a^{-1} $のように使うと、$ x^{-1} \in G $になっている)
二項演算$\cdot$ (積) ($ x,y \in G $に対し $ x・y $のように使うと、$ x・y \in G $になっている)
の組$(G, e, ◌^{-1}, ・ )$で、以下の条件を満たすものを群という
1.単位元は掛けてもなにもしない
$$
e \cdot x = x \cdot e = x \\
$$
2.逆元とくっつくと消える(なにもしない単位元になる)
$$
x \cdot x^{-1} = x^{-1} \cdot x = e
$$
3.結合法則
$$
(x \cdot y) \cdot z = x \cdot (y \cdot z)
$$
これがあるので、$x \cdot y \cdot z$と書く場合があるが、どちらにしてもよいということがわかる。
群Gと集合Xに対して、(左)作用という演算を定義する。
$ g \in G , x \in X $ のとき、 $ gx \in X $ は
- 単位元は作用でも何もしない
$ ex = x $ - 作用は$\cdot$でまとめて作用できる
$ (g_1 \cdot g_2) x = g_1 (g_2 x) $
群の定義と作用の定義より、
$ (g \cdot g^{-1}) x = (g^{-1} \cdot g) x = x $
$ x \sim y \iff あるgによって、 y = gx $ とすると、
- $ x = ex $
- $ y = gx \implies x = g^{-1} y $
- $ z = g_1 y \,かつ\, y = g_2 x \implies z = (g_1 \cdot g_2) x $
なので、同値関係になる。このとき、各同値類を軌道という。
群$G$が集合$X$に作用しているとき、その軌道を$X/G$とする。
また、$G$の元$g$で動かない$X$の点の集合(固定点集合)を $X^g = \{ x | gx = x \}$ と書くとき、
$$
|G| \cdot |X/G| = \sum_{g \in G} |X^g|
$$
($|X|$は$X$の濃度(元の数)を表します。)
\begin{eqnarray} |G| &:& 動かし方の数 \\ |X/G| &:& 同一視をした後のパターン数 \\ |X^g| &:& g \in G で動かしたとき、元のパターンと変わらないものの数 \\ \end{eqnarray}
左辺と右辺とを1対1で対応させる。
まず、同値類ごとに代表として元を1つ選んでおく。$[x]$の代表元を$c_{[x]}と書くことにする。$
右辺 $(g,y) \: (g \in G, y \in X^g)$ が与えられたとする。
$x = c_{[y]}$とすると、$ y \in [y] = [x] $で、$x \sim y$になるので、
ある$h_{y,x}$が存在して$y = h_{y,x} x$と書ける。
右辺から左辺に、$f: (g,y) \mapsto ( g \cdot h_{y,x} , [y])$ という写像で対応させる。
逆に 左辺$(g, [x]) (g \in G, [x] \in X/G)$が与えられたら、
$ x_0 = c_{[x]} $として、
$f': (g, [x]) \mapsto ( g \cdot h_{gx_0,x_0}^{-1} , g x_0 ) $
とすると、
\begin{eqnarray}
f' (f(g,y) ) &=& f'( g \cdot h_{y,c_{[y]}} , [y]) \\
&&(x = c_{[y]}とすると) \\
&=& f'( g \cdot h_{y,x} , [x]) \\
&=& ( g \cdot h_{y,x} \cdot h_{\textcolor{violet}{(g \cdot h_{y,x}) x},x}^{-1} ,\textcolor{violet}{(g \cdot h_{y,x}) x}) \\
&=& ( g \cdot h_{y,x} \cdot h_{\textcolor{violet}{y},x}^{-1} ,\textcolor{violet}{y}) \\
&=& (g,y)
\end{eqnarray}
\begin{eqnarray}
f (f'(g,[x]) ) &=& f( g \cdot h_{gx,x}^{-1} , g x ) \: (xはc_{[x]}を使って代表元のものを選んでおく)\\
&=& ( g \cdot h_{gx,x}^{-1}\cdot h_{gx,x} , [g x] ) \\
&=& (g, [x])
\end{eqnarray}
よって、一対一で対応していることがわかる。
$[x]$から$x$を出すときなどに$c_{[x]}$などを使って、細心の注意を払っているのは、well-defined性といって、
$X/ \sim$などの集合からの関数を作るときは、$x \sim y \implies f([x]) = f([y])$になるようにする必要があり、
そうしないと同じはずの元から違う結果が返ってくるようなことになり、関数にならないという問題があるからです。
赤球、白球がたくさんあるとき、これらのうち6つを円状に並べる方法はいくつあるか。
回転で重なるものは同じとする。
群Gを巡回群$C_6$とする。これは
\begin{eqnarray}
|C_6| &=& \{0,1,2,3,4,5\} \\
e &=& 0 \\
a^{-1} &=& \begin{aligned}
\left\{
\begin{array}{l}
6 - a &\:& ( a > 0) \\
0 &\:& (a = 0)
\end{array}
\right.
\end{aligned}\\
a \cdot b &\equiv& a + b \mod 6\\
\end{eqnarray}
なる群である。
Xを${(0,0,0,0,0,0) \sim (1,1,1,1,1,1) }$の$2^6$要素の集合とし、
作用を$ (gx)_i = x_{(i + g) \bmod 6} $で定義する。
例： $g=3, x = (\textcolor{red}1,\textcolor{blue}0,\textcolor{green}1,\textcolor{purple}0,\textcolor{orange}0,\textcolor{brown}1) $なら、$gx = (\textcolor{purple}0,\textcolor{orange}0,\textcolor{brown}1,\textcolor{red}1,\textcolor{blue}0,\textcolor{green}1)$
そうすると、
- g=0のとき、xのすべての元は動かないので $|X^g| = 64$
- g=1,5のとき、すべてのiについて$x_i = x_{i+1} $でないといけないので、
結局すべての$x_i$が同じ場合のみ重なる $|X^g| = 2$ - g=2,4のとき、$x_0 = x_2 = x_4, x_1 = x_3 = x_5 $ $|X^g| = 4$
- g=3のとき、$x_0 = x_3, x_1 = x_4, x_2 = x_5$ のとき重なるので $|X^g| = 8$
$ | X / G | = \frac{64 + 2 \times 2 + 2 \times 4 + 8}{6} = \frac{84}{6} = 14 $
立方体の6面を赤色、青色、黄色の3色で2面づつ塗り分ける方法は何通りか。
回転で重なるものは同じとする。
群Gを立方体を回転(鏡写しはふくまない)して重ねる方法の全体、
$e$を動かさない操作、
$a^{-1}$をaの逆の回転、
$b \cdot a$をaのあとにbを行う操作とする。
サイコロで考えると、1の行き先が6種類、2はその隣の面4つのどれかなので、24通りの回転があるが、後々のために別の方法で分類する。
- 回転なし(1種)
- 面中心90度回転(6種)
- 面中心180度回転(3種)
- 頂点を1/3周回す(8種)
- 辺の中点を中心に回転し、隣り合う面を入れ替える(6種)
- 選んだ辺の両側、真反対の両側、側面同士が入れ替わる
$X$は立方体を回転を考えずに塗る方法なので、${}_6 C_2 \cdot {}_4 C_2 $要素ある。
$|X^g|$を考える。上の類別ごとに、
- すべて重なる。${}_6 C_2 \cdot {}_4 C_2 $で$90$通り。
- 回転軸以外の4つの面の色が等しい必要があるので不可能。
- 側面の向かい合うペアがそれぞれ等しいので、 軸とそれぞれのペアに割り当てる色を選んで$3!=6$通り
- 回す頂点の周りの3面がそれぞれ等しい必要があるので不可能。
- 選んだ辺の両側、真反対の両側、側面同士が等しいので、それぞれのペアに割り当てる色を選んで$3!=6$通り
$ | X / G | = \frac{90 + 3 \times 6 + 6 \times 6}{24} = \frac{144}{24} = 6 $
立方体の6面を赤色、青色、黄色の3色で塗り分ける方法は何通りか。
使わない色があったり全ての面を同じ色に塗ってもよく、回転で重なるものは同じとする。
$X$は立方体を回転を考えずに塗る方法なので、$3^6$要素ある。
$|X^g|$を考える。上の類別ごとに、
- すべて重なる。$3^6$で$729$通り。
- 回転軸以外の4つの面の色が等しい必要があるので、$3^3$で$27$通り。
- 側面の向かい合うペアがそれぞれ等しいので、 $3^4$で$81$通り。
- 回す頂点の周りの3面がそれぞれ等しいので、 $3^2$で$9$通り。
- 選んだ辺の両側、真反対の両側、側面同士が等しいので、$3^3$で$27$通り
$ | X / G | = \frac{729 + 6 \times 27 + 3 \times 81 + 8 \times 9 + 6 \times 27}{24} = \frac{1368}{24} = 57 $